Problem:
Letter Case PermutationGiven 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.
Solution:
This problem can be solved with traceback.
We use a stringbuffer to store the result string, use an integer to store the current character we are processing. For a position, we can have digit or letter. For digit, we don't have choice but add it to the result stringbuffer. For letter, we can choose to store an Upper case or Lower case letter. So whenever we meet a letter, there is a 2 branch choices. Finally, when the stringbuffer size is equal to the original string size, we add the content to the final result set, then we remove the character we added in the previous step, give the other option a try if there is any.
a A
1 1
b B b B
2 2 2 2
import java.util.*;
class Solution {
Set<String> result = new HashSet<>();
public static void main(String...args) {
Solution sol = new Solution();
sol.solve("a1b2", new StringBuffer(), 0);
for(String s : sol.result)
System.out.println(s);
}
private void solve(String in,StringBuffer sb, int pos) {
if(pos >= in.length()) {
result.add(sb.toString());
return;
}
char c = in.charAt(pos);
if(Character.isDigit(c)) {
sb.append(c);
solve(in, sb, pos+1);
sb.deleteCharAt(sb.length() - 1);
} else {
sb.append(c);
solve(in, sb, pos+1);
sb.deleteCharAt(sb.length() - 1);
sb.append(duel(c));
solve(in, sb, pos+1);
sb.deleteCharAt(sb.length() - 1);
}
}
private char duel(char c) {
if(Character.isUpperCase(c))
return Character.toLowerCase(c);
else
return Character.toUpperCase(c);
}
}
class Solution {
Set<String> result = new HashSet<>();
public static void main(String...args) {
Solution sol = new Solution();
sol.solve("a1b2", new StringBuffer(), 0);
for(String s : sol.result)
System.out.println(s);
}
private void solve(String in,StringBuffer sb, int pos) {
if(pos >= in.length()) {
result.add(sb.toString());
return;
}
char c = in.charAt(pos);
if(Character.isDigit(c)) {
sb.append(c);
solve(in, sb, pos+1);
sb.deleteCharAt(sb.length() - 1);
} else {
sb.append(c);
solve(in, sb, pos+1);
sb.deleteCharAt(sb.length() - 1);
sb.append(duel(c));
solve(in, sb, pos+1);
sb.deleteCharAt(sb.length() - 1);
}
}
private char duel(char c) {
if(Character.isUpperCase(c))
return Character.toLowerCase(c);
else
return Character.toUpperCase(c);
}
}
If there are L letters in the string, we need to deal with 2^L possible states, the time complexity is O(2^L), we only used a stringbuffer to store the temp result, the space complexity is O(string.length()).
