LetterCasePermutation [source code]
public class LetterCasePermutation {
static
/******************************************************************************/
class Solution {
public List<String> letterCasePermutation(String S) {
List<String> res = new ArrayList<> ();
if (S.length () == 0) {
res.add (S);
return res;
}
search (S.toCharArray (), 0, res);
return res;
}
void search (char[] chs, int start, List<String> ls) {
if (start == chs.length) {
ls.add (new String (chs));
return;
}
if (Character.isLetter (chs[start])) {
char old_char = chs[start];
chs[start] = Character.toUpperCase (chs[start]);
search (chs, start + 1, ls);
chs[start] = Character.toLowerCase (chs[start]);
search (chs, start + 1, ls);
chs[start] = old_char;
} else {
search (chs, start + 1, ls);
}
}
}
/******************************************************************************/
public static void main(String[] args) {
LetterCasePermutation.Solution tester = new LetterCasePermutation.Solution();
String[][] inputs = {
{"a1b2"}, {"a1b2", "a1B2", "A1b2", "A1B2"},
{"3z4"}, {"3z4", "3Z4"},
{"12345"}, {"12345"},
{""}, {""},
};
for (int i = 0; i < inputs.length / 2; i++) {
System.out.println (Printer.separator ());
String S = inputs[2 * i][0];
List<String> ans = Arrays.asList (inputs[2 * i + 1]), output = tester.letterCasePermutation (S);
System.out.printf ("%s -> %s, expected: %s\n",
S, Printer.wrap (output.toString(), checkOutput (ans, output) ? 92 : 91), ans
);
}
}
static boolean checkOutput (List<String> ans, List<String> output) {
if (ans.size () != output.size ())
return false;
return new HashSet<> (ans).equals (new HashSet<> (output));
}
}
总感觉这题用backtracking有点太heavyweight了, 但是又想不到更好的办法;
速度10ms (NA);
editorial
Approach #1: Recursion [Accepted]
Intuition
Maintain the correct answer as we increase the size of the prefix of S we are considering.
For example, when S = "abc", maintain ans = [""], and update it to ans = ["a", "A"], ans = ["ab", "Ab", "aB", "AB"], ans = ["abc", "Abc", "aBc", "ABc", "abC", "AbC", "aBC", "ABC"] as we consider the letters "a", "b", "c".
Algorithm
If the next character c is a letter, then we will duplicate all words in our current answer, and add lowercase(c) to every word in the first half, and uppercase(c) to every word in the second half.
If instead c is a digit, we'll add it to every word.
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;
}
}
用iteration的方法写recursion, 这个之前也是见过了; 这题不是一个典型的expand N的题目, 但是还是可以用这种缩小的思路;
他这个循环写的有点意思, 你自己仔细看一下; 当时就加duplicate, 当时就把两个copy都修改了; 因为用的是ArrayList, 所以get其实没有太多的overhead;
Approach #2: Binary Mask [Accepted]
Intuition
Say there are
B letters in the string S. There will be 2^B strings in the answer, which we can represent uniquely by the bitmask bits.
For example, we could represent a7b by 00, a7B by 01, A7b by 10, and A7B by 11. Note that numbers are not part of the bitmask.
Algorithm
For every possible bitmask, construct the correct result to put in the final answer. If the next letter in the word is a letter, write a lowercase or uppercase letter depending on the bitmask. Otherwise, write the digit as given.
class Solution {
public List<String> letterCasePermutation(String S) {
int B = 0;
for (char c: S.toCharArray())
if (Character.isLetter(c))
B++;
List<String> ans = new ArrayList();
for (int bits = 0; bits < 1<<B; 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);
}
}
ans.add(word.toString());
}
return ans;
}
}
还是比较直白的一个思路, 就是自己没有想到; 当然, 对S里面letter的数量有限制; 注意这里他只用bitmask记录letter, 不记录数字, 这样让可以接受的input size又加了不少;
Approach #3: Built-In Library Function [Accepted]
Intuition and Algorithm
A cartesian product of sets is every possible combination of one choice from those sets. For example, {1, 2} x {a, b, c} = {1a, 1b, 1c, 2a, 2b, 2c}.
For languages that have a built-in function to calculate a cartesian product, we can use this function to minimize our work.
class Solution(object):
def letterCasePermutation(self, S):
f = lambda x: (x.lower(), x.upper()) if x.isalpha() else x
return map("".join, itertools.product(*map(f, S)))
When I saw a problem, my first step is to draw a figure. See the figure below:
abc
abc Abc 0
abc aBc Abc ABc 1
abc abC aBc aBC Abc AbC ABc ABC 2There 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).
class 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);
}
}
还真的是写成了一个BFS算法, 很有意思; 能够把BFS抽象理解到这个程度也不简单;
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.
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.
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.
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] += ch[i] < 'a' ? 'a' - 'A' : 'A' - 'a'; // toggle case of charAt(i).
ans.add(String.valueOf(ch)); // append to the end of ans.
}
}
return ans;
}
思路还是一样的, 感觉大家现在这种iteration思路用的都好熟练;
整个代码加上了一些他自己的小技巧, 比如S.charAt(i) > '9'放到了内部for循环的header: 如果不成立, 一个iteration都不执行所以用no-op来完成一个类似continue的操作; 再比如他这里这个toggle的操作, 可以学习一下: 用+差值来进行toggle, 这个其实是一个可以generalize的思路;
看了一会儿之后, 感觉我自己上面的代码可以这样改一下:
class Solution {
public List<String> letterCasePermutation(String S) {
List<String> res = new ArrayList<> ();
if (S.length () == 0) {
res.add (S);
return res;
}
search (S.toCharArray (), 0, res);
return res;
}
void search (char[] chs, int start, List<String> ls) {
if (start == chs.length) {
ls.add (new String (chs));
return;
}
search (chs, start + 1, ls);
if (Character.isLetter (chs[start])) {
char old_letter = letterToggle (chs, start);
search (chs, start + 1, ls);
chs[start] = old_letter;
}
}
char letterToggle (char[] chs, int i) {
char res = chs[i];
chs[i] = Character.isUpperCase (chs[i]) ? Character.toLowerCase (chs[i]) : Character.toUpperCase (chs[i]);
return res;
}
}
感觉这样好看一些了;
Straightforward recursive solution. Simple trick with case toggling.
class Solution {
void backtrack(string &s, int i, vector<string> &res) {
if (i == s.size()) {
res.push_back(s);
return;
}
backtrack(s, i + 1, res);
if (isalpha(s[i])) {
// toggle case
s[i] ^= (1 << 5);
backtrack(s, i + 1, res);
// return previous case
s[i] ^= (1 << 5);
}
}
public:
vector<string> letterCasePermutation(string S) {
vector<string> res;
backtrack(S, 0, res);
return res;
}
};
他这个toggle的做法有点意思啊; 这里也看出来了大小写字母在ASCII表里面的位置的用意了;
Connected to local instance at http://localhost:56846
java> (int) 'a'
java.lang.Integer res0 = 97
java> Integer.toBinaryString (97)
java.lang.String res1 = "1100001"
java> (int) 'A'
java.lang.Integer res2 = 65
java> Integer.toBinaryString (65)
java.lang.String res3 = "1000001"
submission暂时还没有;
Problem Description
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 at most 12.
- S will consist only of letters or digits.
Difficulty:Easy
Total Accepted:1.2K
Total Submissions:2.4K
Contributor:1337c0d3r