题目
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 at most12. -
Swill consist only of letters or digits.
答题
row1: abc
row2: abc Abc
row3: abc aBc Abc ABc
row4: abc abC aBc aBC Abc AbC ABc ABC
有点像我们高中学的排列组合，我们能够知道一共有多少种组合，也知道每一个字母有两种情况，每一个数字有一种情况。
如上图，给出 abc， 我们已经知道有8种组合，根据上一行的组合，只改动一个位置上的字母即可的到本次的组合。以此类推，即可得到最终的所有组合。
另外此题是在考 BFS/DFS 算法，有兴趣的同学可以自行搜索学习。
public List<String> letterCasePermutation(String S) {
if (S == null || S.length() == 0) {
return new ArrayList<String>(Arrays.asList(""));
}
char[] array = S.toCharArray();
int arraySize = array.length;
int count = 0;
for (char ch : array) {
if (Character.isLetter(ch)) {
count++;
}
}
if (count == 0) {
return new ArrayList<String>(Arrays.asList(S));
}
List<String> list = new ArrayList<String>(2 << (count - 1));
list.add(S);
for (int i = 0; i < arraySize; i++) {
char ch = array[i];
if (Character.isDigit(ch)) {
continue;
}
int size = list.size();
for (int j = 0; j < size; j++) {
char[] temp = list.get(j).toCharArray();
if (Character.isUpperCase(ch)) {
temp[i] = Character.toLowerCase(ch);
} else {
temp[i] = Character.toUpperCase(ch);
}
list.add(String.valueOf(temp));
}
}
return list;
}
