784.Letter-Case-Permutation

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.
​
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.

代码

Approach #1 Recursion

class Solution {
public List<String> letterCasePermutation(String S) {
List<StringBuilder> ans = new ArrayList();
ans.add(new StringBuilder());
​
for (char c: S.toCharArray()) {
int n = ans.size();
if (Character.isLetter(c)) {
for (int i = 0; i < n; i++) {
ans.add(new StringBuilder(ans.get(i)));
ans.get(i).append(Character.toLowerCase(c));
ans.get(n + i).append(Character.toUpperCase(c));
}
} else {
for (int i = 0; i < n; i++) {
ans.get(i).append(c);
}
}
}
List<String> finalans = new ArrayList();
for (StringBuilder sb: ans) {
finalans.add(sb.toString());
}
return finalans;
}
}

Approach #2 Binary Mask

class Solution {
public List<String> letterCasePermutation(String S) {
int count = 0;
for (char c: S.toString()) {
if (Character.isLetter(c)) {
count++;
}
}
​
List<String> ans = new ArrayList();
​
for (int bits = 0; bits < 1 << count; bits++) {
int b = 0;
StringBuilder word = new StringBuilder();
for (char letter: S.toCharArray()) {
if (Character.isLetter(letter)) {
if (((bits >> b++) & 1 == 1) {
word.append(Character.toLowerCase(letter));
} else {
word.append(Character.toUpperCase(letter));
}
} else {
word.append(letter);
}
}
}
​
return ans;
}
}