https://leetcode.com/problems/letter-case-permutation/
X. Not efficient
https://leetcode.com/problems/letter-case-permutation/discuss/115607/Very-simple-Java-solution-just-using-Recursion
X.
https://github.com/allaboutjst/airbnb/blob/master/README.md
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.
Examples: Input: S = "a1b2" Output: ["a1b2", "a1B2", "A1b2", "A1B2"] Input: S = "3z4" Output: ["3z4", "3Z4"] Input: S = "12345" Output: ["12345"]
Note:
Swill be a string with length between1and12.Swill consist only of letters or digits.
下面这种解法是官方解答贴的Binary Mask解法，感觉也很巧妙，如果我们仔细观察S = "abc"这个例子，结果会返回8个，为什么是8个呢，因为每个字母都有大小写两种可能，那么三个字母就有2x2x2=8，正好是2的三次方，那么不正好和二进制数相对应么，如果1对应大写字母，0对应小写字母，则有：
000 -> ABC 001 -> ABc 010 -> AbC 011 -> Abc 100 -> aBC 101 -> aBc 110 -> abC 111 -> abc
这样的话，我们只需要先统计出S中字母的个数cnt，然后遍历 [0, 2^cnt) 中的每个数字，对于每个数字，再遍历S中的每个字符，如果是字母，那么如果当前位是1，则加入小写字母，反之加入大写字母；如果是数字，则直接加入即可。我们用j指向位，每次处理完一位后j自增1，表示对下一位进行处理
vector<string> letterCasePermutation(string S) { vector<string> res; int cnt = 0; for (char c : S) { if (c > '9') ++cnt; } for (int i = 0; i < (1 << cnt); ++i) { int j = 0; string word = ""; for (char c : S) { if (c > '9') { if (((i >> j++) & 1) == 1) { word.push_back(tolower(c)); } else { word.push_back(toupper(c)); } } else { word.push_back(c); } } res.push_back(word); } return res; }X. https://leetcode.com/problems/letter-case-permutation/discuss/115671/Java-9-lines-iterative-code-using-backtracking.
toggling letter case changed from ch[i] += ch[i] < 'a' ? 'a' - 'A' : 'A' - 'a' to ch[i] ^= (1 << 5), credit to @tarekd.
Let N be the number of letters in input, for each letter, we can toggle its case to get a new string. That is, there are 2 options for each letter: upper and lower cases. Therefore, we can generate 2 ^ N strings totally in worst case.
The details are as follows:
- Add input into list.
- Iterate through input string, when encountering a) a letter, toggle the case of the corresponding letter in all strings in the current list and append all new strings to list; b) a digit, ignore it.
Let's use "a1b2" as an example, and curly braces below indicate the inside part is(are) new string(s) after togglling operation.
"a1b2" .................................................................................<= initialization
"a1b2" {"A1b2"}....................................................................<= i = 0, a toggled to A
"a1b2" "A1b2".......................................................................<= i = 1, ignore '1', which is a digit,
"a1b2" "A1b2"{"a1B2" "A1B2"}............................................ <= i = 2, b toggled to B
"a1b2" "A1b2" "a1B2" "A1B2".............................................. <= i = 3, ignore '2', which is a digit,
"a1b2" {"A1b2"}....................................................................<= i = 0, a toggled to A
"a1b2" "A1b2".......................................................................<= i = 1, ignore '1', which is a digit,
"a1b2" "A1b2"{"a1B2" "A1B2"}............................................ <= i = 2, b toggled to B
"a1b2" "A1b2" "a1B2" "A1B2".............................................. <= i = 3, ignore '2', which is a digit,
public List<String> letterCasePermutation(String S) {
List<String> ans = new ArrayList<>(Arrays.asList(S));
for (int i = 0; i < S.length(); ++i) { // Traverse string S char by char.
for (int j = 0, sz = ans.size(); S.charAt(i) > '9' && j < sz; ++j) { // S.charAt(i) > '9': letter, not digit.
char[] ch = ans.get(j).toCharArray(); // transform to char[] the string @ j of ans.
ch[i] ^= (1 << 5); // toggle case of charAt(i).
ans.add(String.valueOf(ch)); // append to the end of ans.
}
}
return ans;
}
When I saw a problem, my first step is to draw a figure. See the figure below:
abcabc Abc 0abc aBc Abc ABc 1abc abC aBc aBC Abc AbC ABc ABC 2
There we go! Is that a typical BFS/DFS problem? Yes, you are right!
Be careful to check whether a character is a digit or a letter(lower case or upper case).
Be careful to check whether a character is a digit or a letter(lower case or upper case).
BFS Solution: public List<String> letterCasePermutation(String S) {
if (S == null) {
return new LinkedList<>();
}
Queue<String> queue = new LinkedList<>();
queue.offer(S);
for (int i = 0; i < S.length(); i++) {
if (Character.isDigit(S.charAt(i))) continue;
int size = queue.size();
for (int j = 0; j < size; j++) {
String cur = queue.poll();
char[] chs = cur.toCharArray();
chs[i] = Character.toUpperCase(chs[i]);
queue.offer(String.valueOf(chs));
chs[i] = Character.toLowerCase(chs[i]);
queue.offer(String.valueOf(chs));
}
}
return new LinkedList<>(queue);
}
DFS Solution: public List<String> letterCasePermutation(String S) {
if (S == null) {
return new LinkedList<>();
}
List<String> res = new LinkedList<>();
helper(S.toCharArray(), res, 0);
return res;
}
public void helper(char[] chs, List<String> res, int pos) {
if (pos == chs.length) {
res.add(new String(chs));
return;
}
if (chs[pos] >= '0' && chs[pos] <= '9') {
helper(chs, res, pos + 1);
return;
}
chs[pos] = Character.toLowerCase(chs[pos]);
helper(chs, res, pos + 1);
chs[pos] = Character.toUpperCase(chs[pos]);
helper(chs, res, pos + 1);
}
No need to use a set to handle duplicate values. Thanks to @yik_wai for the suggestion :)
- As soon as you find a letter character at index, check for all its possible combinations by making it a lower case character and an upper case character.
- Add the new char array at the at the end of each recursion.
Example: S="a1b2"
Recursion Tree:
https://zxi.mytechroad.com/blog/searching/leetcode-784-letter-case-permutation/Recursion Tree:
public List<String> letterCasePermutation(String S) {
List<String> ans = new ArrayList<>();
dfs(S.toCharArray(), 0, ans);
return ans;
}
private void dfs(char[] S, int i, List<String> ans) {
if (i == S.length) {
ans.add(new String(S));
return;
}
dfs(S, i + 1, ans);
if (!Character.isLetter(S[i])) return;
S[i] ^= 1 << 5;
dfs(S, i + 1, ans);
S[i] ^= 1 << 5;
}
X. Not efficient
https://leetcode.com/problems/letter-case-permutation/discuss/115607/Very-simple-Java-solution-just-using-Recursion
public List<String> letterCasePermutation(String S) {
List<String> list = new ArrayList<>();
if (S == null || S.length() == 0) {
list.add("");
return list;
}
List<String> results = letterCasePermutation(S.substring(1));
for (String result : results) {
if (Character.isLetter(S.charAt(0))) {
list.add(S.substring(0, 1).toLowerCase() + result);
list.add(S.substring(0, 1).toUpperCase() + result);
} else {
list.add(S.substring(0, 1) + result);
}
}
return list;
}X.
https://github.com/allaboutjst/airbnb/blob/master/README.md
Find all the combinations of a string in lowercase and uppercase. For example, string "ab" >>> "ab", "Ab", "aB", "AB". So, you will have 2^n (n = number of chars in the string) output strings. The goal is for you to test each of these strings and see if it matchs a hidden string.
private boolean isBitSet(int n, int offset) {
return (n >> offset & 1) != 0;
}
public List<String> strComb(String text) {
List<String> res = new ArrayList<>();
if (text == null || text.length() == 0) {
return res;
}
char[] chars = text.toCharArray();
for (int i = 0, n = (int) Math.pow(2, chars.length); i < n; i++) {
char[] curr = new char[chars.length];
for (int j = 0; j < chars.length; j++) {
curr[j] = (isBitSet(i, j)) ? Character.toUpperCase(chars[j]) : Character.toLowerCase(chars[j]);
}
res.add(new String(curr));
}
return res;
}
}
