784_Letter_Case_Permutation

qiyuangong · qiyuangong · commit 542f13fc6798 · 2018-12-26T11:01:29.000+08:00
diff --git a/README.md b/README.md
@@ -184,6 +184,7 @@ Also, there are open source implementations for basic data structs and algorithm
 | 760 | [Find Anagram Mappings](https://leetcode.com/problems/find-anagram-mappings/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/760_Find_Anagram_Mappings.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/760_Find_Anagram_Mappings.java) | Hash table with A's (val, index), O(n) and O(n) |
 | 766 | [Toeplitz Matrix](https://leetcode.com/problems/toeplitz-matrix/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/766_Toeplitz_Matrix.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/766_Toeplitz_Matrix.java) | Check from top left to bottom right, i,j == i + 1, j + 1. |
 | 771 | [Jewels and Stones](https://leetcode.com/problems/jewels-and-stones/description/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/771_Jewels_and_Stones.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/771_Jewels_and_Stones.java) | Count given char in string. Hash or table. [Oneline](https://leetcode.com/problems/jewels-and-stones/discuss/113574/1-liners-PythonJavaRuby) |
+| 784 | [Letter Case Permutation](https://leetcode.com/problems/letter-case-permutation/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/784_Letter_Case_Permutation.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/784_Letter_Case_Permutation.java) | Note that this is a 2^n problem. 1. Recursively generate result with previous result <br> 2. Bin Mask, number of zeor equal to number of alpha<br>3. Python build in product. |
 | 804 | [Unique Morse Code Words](https://leetcode.com/problems/unique-morse-code-words/description/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/804_Unique_Morse_Code_Words.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/804_Unique_Morse_Code_Words.java) | String, Hash and Set. Set is recommended. |
 | 811 | [Subdomain Visit Count](https://leetcode.com/problems/subdomain-visit-count/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/811_Subdomain_Visit_Count.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/811_Subdomain_Visit_Count.java) | String split and HashMap, O(n) and O(n) |
 | 819 | [Most Common Word](https://leetcode.com/problems/most-common-word/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/819_Most_Common_Word.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/819_Most_Common_Word.java) | String processing, be careful about 'b,b,b'. regex is recommended. |
diff --git a/java/784_Letter_Case_Permutation.java b/java/784_Letter_Case_Permutation.java
@@ -0,0 +1,54 @@
+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;
+    }
+
+    /*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;
+
+    }*/
+}
diff --git a/python/784_Letter_Case_Permutation.py b/python/784_Letter_Case_Permutation.py
@@ -0,0 +1,39 @@
+class Solution(object):
+    # def letterCasePermutation(self, S):
+    #     ans = [[]]
+
+    #     for char in S:
+    #         n = len(ans)
+    #         if char.isalpha():
+    #             # Double the ans
+    #             for i in xrange(n):
+    #                 ans.append(ans[i][:])
+    #                 ans[i].append(char.lower())
+    #                 ans[n + i].append(char.upper())
+    #         else:
+    #             # Normal append
+    #             for i in xrange(n):
+    #                 ans[i].append(char)
+
+    #     return map("".join, ans)
+
+    def letterCasePermutation(self, S):
+        B = sum(letter.isalpha() for letter in S)
+        ans = []
+
+        for bits in xrange(1 << B):
+            b = 0
+            word = []
+            for letter in S:
+                if letter.isalpha():
+                    if (bits >> b) & 1:
+                        word.append(letter.lower())
+                    else:
+                        word.append(letter.upper())
+
+                    b += 1
+                else:
+                    word.append(letter)
+
+            ans.append("".join(word))
+        return ans
