leetcode 784. Letter Case Permutation 字母大小写全排列

Problem: 784. Letter Case Permutation 字母大小写全排列

解题过程

两种方案的，1、回溯，每次替换即可 2、位运算，整数的二进制1代表反转，去重即可的

Code

class Solution { public: vector<string> tr; unordered_map<string, bool> ump; int ch[16]; void dfs(string s, int cnt) { if(ump.count(s)==0) { tr.push_back(s); } ump[s] = true; if(cnt==s.size()) return; if(ch[cnt] < 0) { dfs(s, cnt + 1); } else { s[cnt] = tolower(s[cnt]); dfs(s, cnt + 1); s[cnt] = toupper(s[cnt]); dfs(s, cnt + 1); } } vector<string> letterCasePermutation(string s) { for(int i = 0; i < s.size(); i++) { if(isdigit(s[i])) { ch[i] = -1; } else if(s[i]>='a' && s[i]<='z') { ch[i] = 1; } else { ch[i] = 2; } } dfs(s, 0); return tr; int n = s.size(); unsigned int end = pow(2, n) - 1, tmp; unordered_map<char, char> pam; for(char c = 'a'; c <= 'z'; c++) { pam[c] = toupper(c); } for(char c = 'A'; c <= 'Z'; c++) { pam[c] = tolower(c); } string pre, tail, scp = s; // tr.push_back(s); unordered_set<string> ret; ret.insert(s); for(unsigned int i = 0; i <= end; i++) { tmp = i; s = scp; for(int j = 0; j < n; j++) { if( (tmp&1) == 1 && isalpha(s[j]) ) { s[j] = pam[s[j]]; ret.insert(s); } else if((tmp&1) == 1 && isdigit(s[j])){ break; } tmp = ( tmp >> 1 ); } } for(auto& k : ret) { tr.push_back(k); } return tr; } };