05 August 2008
给一个string，有数字和字母，可以改变里面的字母大小写，组成不同的字符串，一共有多少种组合
46-permutations的变种
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
class Solution {
public List<String> letterCasePermutation(String s) {
List<String> results = new ArrayList<>();
if (s.isEmpty()) {
return results;
}
backtrack(results, new StringBuilder(s), 0);
return results;
}
private void backtrack(List<String> results, StringBuilder s, int index) {
if (index == s.length()) {
results.add(s.toString());
return;
}
char curr = s.charAt(index);
//选择1 - 不改变当前字母
backtrack(results, s, index + 1);
//选择2：改为大写或者小写(前提是字母)
if((curr >='A' && curr <= 'Z') || (curr >= 'a' && curr <= 'z')) {
if(curr <= 'Z') {
s.setCharAt(index, (char)(curr + 32));
} else {
s.setCharAt(index, (char)(curr - 32));
}
backtrack(results, s, index + 1);
}
}
}
也可以直接BFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
/*
BFS或DFS
https://leetcode.com/problems/letter-case-permutation/discuss/115485/Java-Easy-BFS-DFS-solution-with-explanation
*/
public List<String> letterCasePermutation(String S) {
LinkedList<String> r = new LinkedList<>();
r.add(S);
for (int i = 0; i < S.length(); i++) {
char c = S.charAt(i);
if (Character.isLetter(c)) {
int size = r.size();
for (;size > 0; size--) {
String s = r.poll();
String left = s.substring(0, i), right = s.substring(i + 1);
r.add(left + Character.toLowerCase(c) + right);
r.add(left + Character.toUpperCase(c) + right);
}
}
}
return r;
}
}