update

1 files changed, 93 insertions, 0 deletions

diff --git a/916/main.py b/916/main.py
new file mode 100755
index 0000000..89d1ad1
--- /dev/null
+++ b/916/main.py
@@ -0,0 +1,93 @@
+#!/usr/bin/env python3
+
+import copy
+from typing import List, Dict
+
+
+class Solution:
+    def wordSubsets_v2(
+        self, words1: List[str], words2: List[str]
+    ) -> List[str]:
+        """Way too slow.Way too stupid."""
+        words2_maps: List[Dict] = []
+        result: List[str] = []
+
+        def get_map(word):
+            word_map: Dict[str, int] = {}
+            for char in word:
+                if char in word_map:
+                    word_map[char] = word_map[char] + 1
+                else:
+                    word_map[char] = 1
+
+            return word_map
+
+        for word in words2:
+            words2_maps.append(get_map(word))
+        word_map: Dict[str, int] = {}
+        for word in words1:
+            for char in word:
+                if char in word_map:
+                    word_map[char] = word_map[char] + 1
+                else:
+                    word_map[char] = 1
+            is_matching = True
+            for word2_map in words2_maps:
+                for k, v in word2_map.items():
+                    if k in word_map:
+                        if v <= word_map[k]:
+                            pass
+                        else:
+                            is_matching = False
+                            break
+                    else:
+                        is_matching = False
+                        break
+                if is_matching:
+                    pass
+                else:
+                    break
+            if is_matching:
+                result.append(word)
+            # words1_maps.append(copy.deepcopy(word_map))
+            word_map = {}
+            is_matching = False
+
+        return result
+
+    def wordSubsets(self, A: List[str], B: List[str]) -> List[str]:
+        def count(word):
+            ans = [0] * 26
+            for c in word:
+                ans[ord(c) - ord("a")] += 1
+            return ans
+
+        bmax = [0] * 26
+        for b in B:
+            ls = count(b)
+            for i in range(26):
+                bmax[i] = max(bmax[i], ls[i])
+
+        ans = []
+        for a in A:
+            ls = count(a)
+            for i in range(26):
+                if ls[i] < bmax[i]:
+                    break
+            else:
+                ans.append(a)
+        return ans
+
+
+def main():
+    words1 = ["amazon", "apple", "facebook", "google", "leetcode"]
+    words2 = ["e", "o"]
+    words3 = ["amazon", "apple", "facebook", "google", "leetcode"]
+    words4 = ["l", "e"]
+    solution = Solution()
+    print(solution.wordSubsets(words1, words2))
+    print(solution.wordSubsets(words3, words4))
+
+
+if __name__ == "__main__":
+    main()