784. Letter Case Permutation

发表于 | 分类于 | 浏览 次

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.

1
2
3
4
5
6
7
8
9
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 will consist only of letters or digits.

解法一：回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    vector<string> letterCasePermutation(string S) {
        string tmp;
        vector<string> res;
        dfs(S, tmp, res, 0);
        return res;
    }
    void dfs(string &s, string &tmp,vector<string> &res, int pos){
        if(pos == s.size()){
            res.push_back(tmp);
            return ;
        }
        
        // 如果是数字，直接加入
        if(s[pos] >= '0' && s[pos] <= '9'){
            tmp.push_back(s[pos]);
            dfs(s, tmp, res, pos + 1);
            tmp.pop_back();
        }else{        
            // 如果是英文字母，分别加入小写形式和大写形式
            tmp.push_back(tolower(s[pos]));
            dfs(s, tmp, res, pos + 1);
            tmp.pop_back();
            
            tmp.push_back(toupper(s[pos]));
            dfs(s, tmp, res, pos + 1);
           tmp.pop_back();
        }
    }
};

解法二：bit manipulation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    vector<string> letterCasePermutation(string S) {
        int sum = 1;
        for(int i=0;i<S.size();++i){
            if(isalpha(S[i])){  // check if a char is a alphabetic
                sum *= 2;
            }
        }
        
        vector<string> res;
        string tmp;
        int tmpSum = 0;
        for(int i=0;i<sum;++i){
            tmpSum = i;
            tmp = S;
            for(int j=0;j<S.size();++j){
                if(isalpha(S[j])){
                    if(tmpSum & 1)  // tmpSum[j] == 1
                        tmp[j] = toupper(S[j]);
                    else
                        tmp[j] = tolower(S[j]);
                    tmpSum /= 2;        // tmpSum right move
                }
            }
            res.push_back(tmp);
        }
        return res;
    }
};