952 Word Subsets
952 Word Subsets
Word Subsets 
You are given two string arrays words1 and words2.
A string b is a subset of string a if every letter in b occurs in a including multiplicity.
1
For example, "wrr" is a subset of "warrior" but is not a subset of "world".
A string a from words1 is universal if for every string b in words2, b is a subset of a.
Return an array of all the universal strings in words1. You may return the answer in any order.
Example 1:
1
2
3
4
**Input:** words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["e","o"]
**Output:** ["facebook","google","leetcode"]
Example 2:
1
2
3
4
**Input:** words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["l","e"]
**Output:** ["apple","google","leetcode"]
Constraints:
1
2
3
4
1 <= words1.length, words2.length <= 104
1 <= words1[i].length, words2[i].length <= 10
words1[i] and words2[i] consist only of lowercase English letters.
All the strings of words1 are **unique**.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
class Node:
def __init__(self):
self.ls = []
self.dt = {}
def print1(self):
print(self.dt.values(), self.ls)
class Tree:
def __init__(self):
self.root = Node()
def insert_traverse(self, root, s, id):
if len(s) == 0:
return
for k in s:
if k not in root.dt:
root.dt[k] = (set(), Node())
root.dt[k][0].add(id)
else:
root.dt[k][0].add(id)
#root.print1()
self.insert_traverse(root.dt[s[0]][1], s[1:], id)
def insert(self, s, id):
root = self.root
self.insert_traverse(root, s, id)
def traverse_compare(self, root, s1, n):
if len(s1) == 0:
return n
if s1[0] in root.dt:
print(root.dt[s1[0]][0])
return self.traverse_compare(root.dt[s1[0]][1], s1[1:], root.dt[s1[0]][0])
return None
def compare(self, s1):
root = self.root
return self.traverse_compare(root, s1, -1)
class Solution:
def wordSubsets(self, A: List[str], B: List[str]) -> List[str]:
bmax = [0] * 26
for b in B:
tempb = [0] * 26
for i, c in enumerate(b):
tempb[ord(c) - ord('a')] += 1
for i, m in enumerate(tempb):
bmax[i] = max(bmax[i], tempb[i])
res = []
for a in A:
amax = [0] * 26
for i in a:
amax[ord(i) - ord('a')] += 1
t = True
for x, y in zip(amax, bmax):
if x < y:
t = False
break
if t:
res.append(a)
return res
dt = {}
t = Tree()
arr = [0] * 26
for idx, word in enumerate(words1):
for k in word:
if arr[ord(k) - ord('a')] == 0:
arr[ord(k) - ord('a')] = {}
if idx in arr[ord(k) - ord('a')]:
arr[ord(k) - ord('a')][idx] += 1
else:
arr[ord(k) - ord('a')][idx] = 1
m = [0] * len(words1)
s = "".join(words2)
for idx, word in enumerate(words2):
arr1 = copy.deepcopy(arr)
for k in word:
if arr1[ord(k) - ord('a')] != 0:
for n in arr1[ord(k) - ord('a')].keys():
if arr1[ord(k) - ord('a')][n] > 0:
m[n] += 1
arr1[ord(k) - ord('a')][n] -= 1
res = []
s = "".join(words2)
for idx, k in enumerate(m):
if k == len(s):
res.append(words1[idx])
return res
for idx, word in enumerate(words2):
print("---", t.compare(word))
for k in t.compare(word) if t.compare(word) != None else []:
m[k] += 1
print("m", m)
for idx, word in enumerate(words1):
word = sorted(word)
i = 0
j = 0
while(i < len(word)): # only 10 times
j = i
while(j < len(word)): # only 10 times
if "".join(word[i:j+1]) not in dt:
dt["".join(word[i:j+1])] = set()
if idx not in dt["".join(word[i:j+1])]:
dt["".join(word[i:j+1])].add(idx)
j += 1
i += 1
for idx, word in enumerate(words2): #can happen m times
word = "".join(sorted(word))
if word in dt:
for k in dt[word]: # can happen n times
m[k] += 1
res = []
print(m)
for idx, k in enumerate(m):
if k == len(words2):
res.append(words1[idx])
return res
"""
["amazon","apple","facebook","google","leetcode"], words2 = ["ebo","ok"]
"""
This post is licensed under CC BY 4.0 by the author.