Array
Hash Table
String
Description
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.
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:
Input: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["e","o"]
Output: ["facebook","google","leetcode"]
Example 2:
Input: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["l","e"]
Output: ["apple","google","leetcode"]
Constraints:
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 .
Solutions
Solution 1: Counting
Traverse each word b
in words2
, count the maximum occurrence of each letter, and record it as cnt
.
Then traverse each word a
in words1
, count the occurrence of each letter, and record it as t
. If the occurrence of each letter in cnt
is not greater than the occurrence in t
, then a
is a universal word, and add it to the answer.
The time complexity is $O(L)$, where $L$ is the sum of the lengths of all words in words1
and words2
.
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13 class Solution :
def wordSubsets ( self , words1 : List [ str ], words2 : List [ str ]) -> List [ str ]:
cnt = Counter ()
for b in words2 :
t = Counter ( b )
for c , v in t . items ():
cnt [ c ] = max ( cnt [ c ], v )
ans = []
for a in words1 :
t = Counter ( a )
if all ( v <= t [ c ] for c , v in cnt . items ()):
ans . append ( a )
return ans
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 class Solution {
public List < String > wordSubsets ( String [] words1 , String [] words2 ) {
int [] cnt = new int [ 26 ] ;
for ( var b : words2 ) {
int [] t = new int [ 26 ] ;
for ( int i = 0 ; i < b . length (); ++ i ) {
t [ b . charAt ( i ) - 'a' ]++ ;
}
for ( int i = 0 ; i < 26 ; ++ i ) {
cnt [ i ] = Math . max ( cnt [ i ] , t [ i ] );
}
}
List < String > ans = new ArrayList <> ();
for ( var a : words1 ) {
int [] t = new int [ 26 ] ;
for ( int i = 0 ; i < a . length (); ++ i ) {
t [ a . charAt ( i ) - 'a' ]++ ;
}
boolean ok = true ;
for ( int i = 0 ; i < 26 ; ++ i ) {
if ( cnt [ i ] > t [ i ] ) {
ok = false ;
break ;
}
}
if ( ok ) {
ans . add ( a );
}
}
return ans ;
}
}
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 class Solution {
public :
vector < string > wordSubsets ( vector < string >& words1 , vector < string >& words2 ) {
int cnt [ 26 ] = { 0 };
int t [ 26 ];
for ( auto & b : words2 ) {
memset ( t , 0 , sizeof t );
for ( auto & c : b ) {
t [ c - 'a' ] ++ ;
}
for ( int i = 0 ; i < 26 ; ++ i ) {
cnt [ i ] = max ( cnt [ i ], t [ i ]);
}
}
vector < string > ans ;
for ( auto & a : words1 ) {
memset ( t , 0 , sizeof t );
for ( auto & c : a ) {
t [ c - 'a' ] ++ ;
}
bool ok = true ;
for ( int i = 0 ; i < 26 ; ++ i ) {
if ( cnt [ i ] > t [ i ]) {
ok = false ;
break ;
}
}
if ( ok ) {
ans . emplace_back ( a );
}
}
return ans ;
}
};
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 func wordSubsets ( words1 [] string , words2 [] string ) ( ans [] string ) {
cnt := [ 26 ] int {}
for _ , b := range words2 {
t := [ 26 ] int {}
for _ , c := range b {
t [ c - 'a' ] ++
}
for i := range cnt {
cnt [ i ] = max ( cnt [ i ], t [ i ])
}
}
for _ , a := range words1 {
t := [ 26 ] int {}
for _ , c := range a {
t [ c - 'a' ] ++
}
ok := true
for i , v := range cnt {
if v > t [ i ] {
ok = false
break
}
}
if ok {
ans = append ( ans , a )
}
}
return
}
GitHub