C++ ] leetCode 784 - Letter Case Permutation

 

 

Given a string s, you can transform every letter individually to be lowercase or uppercase to create another string. Return a list of all possible strings we could create. Return the output in any order. 

 

 

Example 1: 

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

 

 

Example 2: 

• Input: s = "3z4" 
• Output: ["3z4","3Z4"] 

 

 

Constraints: 

• 1 <= s.length <= 12 
• s consists of lowercase English letters, uppercase English letters, and digits.

 

주어진 문자열에서 알파벳을 대문자 또는 소문자로 변환하여 만들 수 있는 모든 다른 문자열의 집합을 벡터로 반환하는 문제이다. 

 

알파벳은 대문자/소문자 2개의 경우의 수가 있고 등장하는 알파벳 개수에 따라 생성가능한 모든 조합의 수는 2의 '알파벳 개수'승 이다. 2 << '알파벳 개수' 만큼 반복해서 푸는 방법도 있겠지만 직관성이 떨어져 재귀함수를 사용해서 풀었다.

 

재귀함수 createAnotherString은 0부터 시작하는 idx와 최초 주어진 문자열 original, 재귀를 반복하면서 만들 문자열 s 그리고 문자열 조합을 집어넣을 벡터 ss를 파라미터로 받는다.

 

재귀함수는 기본적으로 base case와 recursive case의 두 부분으로 나뉘는데, base case는 재귀 호출을 멈추는 조건을 정의하고, recursive case는 자기 자신의 함수 호출를 호출하는 부분을 말한다.

 

base case인 if(idx == original.length()) { } 구문에서는 현재까지 완성한 문자열 s를 문자열 벡터에 집어 넣는다.

 

그 외 recursive case에서는 해당 인덱스의 문자가 알파벳이 아닌 경우 idx를 1 증가하고 s에는 해당 문자를 추가하며 자기 자신을 호출하고, 해당 인덱스의 문자가 알파벳인 경우 idx를 1 증가하고 s에는 해당 알파벳의 소문자 또는 대문자를 추가하며 2번 호출한다.

 

 

 

 

class Solution {
public:
    void createAnotherString(int idx, string& original, string s, vector<string>& ss) {
        if(idx == original.length()) {
            ss.push_back(s);
            return;
        }
        
        char ch = original[idx];

        // 알파벳인 경우
        if((ch >= 0x41 && ch <= 0x5a || (ch >= 0x61 && ch <= 0x7a))) {
            createAnotherString(idx + 1, original, s + ch, ss);
            // 대소문자 변환
            ch = ch >= 0x61 ? ch - 0x20 : ch + 0x20;
            createAnotherString(idx + 1, original, s + ch, ss);
        }
        // 알파벳이 아닌 경우
        else {
            createAnotherString(idx + 1, original, s + ch, ss);
        }
    }

    vector<string> letterCasePermutation(string s) {
        vector<string> ss;
        createAnotherString(0, s, "", ss);
        return ss;        
    }
};