문제

Given a string S, we can transform every letter individually to be lowercase or uppercase to create another string. Return a list of all possible strings we could create.

문자열 S가 주어지면 모든 문자를 개별적으로 소문자 또는 대문자로 변환하여 다른 문자열을 만들 수 있습니다. 우리가 만들 수있는 모든 가능한 문자열의 목록을 반환합니다.

Examples :

Input : S = "a1b2"
Output : ["a1b2", "a1B2", "A1b2", "A1B2"]

Input : S = "3z4"
Output : ["3z4", "3Z4"]

Input : S = "12345"
Output : ["12345"]

Note :

S will be a string with length between 1 and 12 S는 길이가 1에서 12 사이 인 문자열입니다.
S will consist only of letters or digits. S는 문자 또는 숫자로만 구성됩니다.

기본 지식

백트래킹(back tracking) :

모든 경우의 수를 전부 고려하는 알고리즘이다. 일종의 트리 탐색 알고리즘이라고 봐도 된다. 구조적으로 깊이우선탐색을 기반으로 한다. 즉, DFS의 구조를 적용할 수 있는 문제에 적용될 수 있다.

백트래킹을 쉽게 설명하자면 어떤 노드의 유망성을 점검하고 유망하지 않으면 그 노드의 부모 노드로 돌아간 후 다른 자손의 노드를 검색하는 것을 말한다. 즉, 스택에 자식노드를 넣기 전에 유망한지(해답이 될 가능성이 있는지) 확인하고 스택에 넣음을 말한다.

풀이

이 문제의 핵심은 재귀호출(recursive call)로 해당 인덱스가 알파벳이면 하나는 소문자, 하나는 대문자로 배열을 저장하고 각각 다시 재귀호출을 하여 여러 가지의 경우의 수를 만드는 것입니다.

재귀호출을 할 때 주의할 점은 stop condition을 만들어 줘야 하는 것입니다. 재귀호출 특성상 stop condition을 지정해놓지 않으면 무한 반복할 것입니다.

Answer :

class Solution {
    public List<String> letterCasePermutation(String S) {
        char[] arr = S.toCharArray();
        List<String> ret = new ArrayList<>();
        backtrack(arr, ret, 0);
        return ret;
    }
    public void backtrack(char[] arr, List<String> ret, int idx){
        if(idx==arr.length){                //recursive call Stop condition
            ret.add(new String(arr));   
        }else{
            char a = arr[idx];
            if(isAlpha(a)){
                arr[idx] = Character.toLowerCase(a);
                backtrack(arr,ret,idx+1);
                arr[idx] = Character.toUpperCase(a);
                backtrack(arr,ret,idx+1);
            }else{
                backtrack(arr,ret,idx+1);
            }
        }
    }
    public boolean isAlpha(char c){
        return (c>='a' && c<='z') || (c>='A' && c<='Z');
    }
}

첫 번째 인덱스부터 isAlpha함수로 알파벳인지 확인하고, 알파벳이라면 arr[0]에 소문자를 대입하고 다음 인덱스로recursivecall, arr[0]에 대문자를 대입하고 다음 인덱스로 recursivecall을 합니다.
위와 같은 방법으로 알파벳이면 소문자, 대문자로 각각 대입하고 다음 인덱스로 recursivecall을 함으로 각각의 경우의 수를 만들어갑니다.
재귀호출의 stop condition으로 문자열의 끝(arr.length)까지 문자열(arr)을 채웠으면 결과 문자열의 집합 ret에 추가해줍니다. (ret.add(new String(arr))

출처 : 제가 알고리즘 문제에 막 감을 익히고 있는 단계여서 유튜버 승지니어님의 코드를 많이 인용하였습니다. 도움되는 영상이 많이 있으므로 많은 방문 부탁드리겠습니다.

유튜브 승지니어 해당영상

← Previous Post Next Post →

LeetCode#784

Letter Case Permutation

문제

기본 지식

풀이