Depth-First Search
Trie
Description
Given an array of strings words
, find the longest string in words
such that every prefix of it is also in words
.
For example, let words = ["a", "app", "ap"]
. The string "app"
has prefixes "ap"
and "a"
, all of which are in words
.
Return the string described above. If there is more than one string with the same length, return the lexicographically smallest one, and if no string exists, return ""
.
Example 1:
Input: words = ["k","ki","kir","kira", "kiran"]
Output: "kiran"
Explanation: "kiran" has prefixes "kira", "kir", "ki", and "k", and all of them appear in words.
Example 2:
Input: words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
Output: "apple"
Explanation: Both "apple" and "apply" have all their prefixes in words.
However, "apple" is lexicographically smaller, so we return that.
Example 3:
Input: words = ["abc", "bc", "ab", "qwe"]
Output: ""
Constraints:
1 <= words.length <= 105
1 <= words[i].length <= 105
1 <= sum(words[i].length) <= 105
words[i]
consists only of lowercase English letters.
Solutions
Solution 1: Trie
We define a trie, each node of the trie has two attributes, one is a children
array of length $26$, and the other is a isEnd
flag indicating whether it is the end of a word.
We traverse words
, for each word w
, we start traversing from the root node. If the current node's children
array does not contain the first character of w
, we create a new node, then continue to traverse the next character of w
, until we finish traversing w
, we mark the isEnd
of the current node as true
.
Next, we traverse words
, for each word w
, we start traversing from the root node. If the isEnd
field of the current node's children
array is false
, it means that some prefix of w
is not in words
, we return false
. Otherwise, we continue to traverse the next character of w
, until we finish traversing w
, we return true
.
The time complexity is $O(\sum_{w \in words} |w|)$, and the space complexity is $O(\sum_{w \in words} |w|)$.
Python3 Java C++ Go TypeScript Rust C#
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 class Trie :
__slots__ = [ "children" , "is_end" ]
def __init__ ( self ):
self . children : List [ Trie | None ] = [ None ] * 26
self . is_end : bool = False
def insert ( self , w : str ) -> None :
node = self
for c in w :
idx = ord ( c ) - ord ( "a" )
if not node . children [ idx ]:
node . children [ idx ] = Trie ()
node = node . children [ idx ]
node . is_end = True
def search ( self , w : str ) -> bool :
node = self
for c in w :
idx = ord ( c ) - ord ( "a" )
node = node . children [ idx ]
if not node . is_end :
return False
return True
class Solution :
def longestWord ( self , words : List [ str ]) -> str :
trie = Trie ()
for w in words :
trie . insert ( w )
ans = ""
for w in words :
if ( len ( w ) > len ( ans ) or len ( w ) == len ( ans ) and w < ans ) and trie . search ( w ):
ans = w
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48 class Trie {
private Trie [] children = new Trie [ 26 ] ;
private boolean isEnd ;
public Trie () {
}
public void insert ( String w ) {
Trie node = this ;
for ( char c : w . toCharArray ()) {
int idx = c - 'a' ;
if ( node . children [ idx ] == null ) {
node . children [ idx ] = new Trie ();
}
node = node . children [ idx ] ;
}
node . isEnd = true ;
}
public boolean search ( String w ) {
Trie node = this ;
for ( char c : w . toCharArray ()) {
int idx = c - 'a' ;
node = node . children [ idx ] ;
if ( ! node . isEnd ) {
return false ;
}
}
return true ;
}
}
class Solution {
public String longestWord ( String [] words ) {
Trie trie = new Trie ();
for ( String w : words ) {
trie . insert ( w );
}
String ans = "" ;
for ( String w : words ) {
if (( w . length () > ans . length () || ( w . length () == ans . length () && w . compareTo ( ans ) < 0 ))
&& trie . search ( w )) {
ans = w ;
}
}
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51 class Trie {
private :
Trie * children [ 26 ];
bool isEnd = false ;
public :
Trie () {
fill ( begin ( children ), end ( children ), nullptr );
}
void insert ( const string & w ) {
Trie * node = this ;
for ( char c : w ) {
int idx = c - 'a' ;
if ( ! node -> children [ idx ]) {
node -> children [ idx ] = new Trie ();
}
node = node -> children [ idx ];
}
node -> isEnd = true ;
}
bool search ( const string & w ) {
Trie * node = this ;
for ( char c : w ) {
int idx = c - 'a' ;
node = node -> children [ idx ];
if ( ! node -> isEnd ) {
return false ;
}
}
return true ;
}
};
class Solution {
public :
string longestWord ( vector < string >& words ) {
Trie trie ;
for ( const string & w : words ) {
trie . insert ( w );
}
string ans = "" ;
for ( const string & w : words ) {
if (( w . size () > ans . size () || ( w . size () == ans . size () && w < ans )) && trie . search ( w )) {
ans = w ;
}
}
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
35
36
37
38
39
40
41
42
43
44
45
46 type Trie struct {
children [ 26 ] * Trie
isEnd bool
}
func newTrie () * Trie {
return & Trie {}
}
func ( t * Trie ) insert ( w string ) {
node := t
for _ , c := range w {
idx := c - 'a'
if node . children [ idx ] == nil {
node . children [ idx ] = newTrie ()
}
node = node . children [ idx ]
}
node . isEnd = true
}
func ( t * Trie ) search ( w string ) bool {
node := t
for _ , c := range w {
idx := c - 'a'
node = node . children [ idx ]
if ! node . isEnd {
return false
}
}
return true
}
func longestWord ( words [] string ) string {
trie := newTrie ()
for _ , w := range words {
trie . insert ( w )
}
ans := ""
for _ , w := range words {
if ( len ( w ) > len ( ans ) || ( len ( w ) == len ( ans ) && w < ans )) && trie . search ( w ) {
ans = w
}
}
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
35
36
37
38
39
40
41
42 class Trie {
private children : ( Trie | null )[] = Array ( 26 ). fill ( null );
private isEnd : boolean = false ;
insert ( w : string ) : void {
let node : Trie = this ;
for ( const c of w ) {
const idx : number = c . charCodeAt ( 0 ) - 'a' . charCodeAt ( 0 );
if ( ! node . children [ idx ]) {
node . children [ idx ] = new Trie ();
}
node = node . children [ idx ] as Trie ;
}
node . isEnd = true ;
}
search ( w : string ) : boolean {
let node : Trie = this ;
for ( const c of w ) {
const idx : number = c . charCodeAt ( 0 ) - 'a' . charCodeAt ( 0 );
node = node . children [ idx ] as Trie ;
if ( ! node . isEnd ) {
return false ;
}
}
return true ;
}
}
function longestWord ( words : string []) : string {
const trie : Trie = new Trie ();
for ( const w of words ) {
trie . insert ( w );
}
let ans : string = '' ;
for ( const w of words ) {
if (( w . length > ans . length || ( w . length === ans . length && w < ans )) && trie . search ( w )) {
ans = w ;
}
}
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52 struct Trie {
children : [ Option < Box < Trie >> ; 26 ],
is_end : bool ,
}
impl Trie {
fn new () -> Self {
Trie {
children : Default :: default (),
is_end : false ,
}
}
fn insert ( & mut self , w : & str ) {
let mut node = self ;
for c in w . chars () {
let idx = ( c as usize ) - ( 'a' as usize );
node = node . children [ idx ]. get_or_insert_with ( || Box :: new ( Trie :: new ()));
}
node . is_end = true ;
}
fn search ( & self , w : & str ) -> bool {
let mut node = self ;
for c in w . chars () {
let idx = ( c as usize ) - ( 'a' as usize );
if let Some ( next_node ) = & node . children [ idx ] {
node = next_node . as_ref ();
if ! node . is_end {
return false ;
}
}
}
true
}
}
impl Solution {
pub fn longest_word ( words : Vec < String > ) -> String {
let mut trie = Trie :: new ();
for w in & words {
trie . insert ( w );
}
let mut ans = String :: new ();
for w in & words {
if ( w . len () > ans . len () || ( w . len () == ans . len () && w < & ans )) && trie . search ( w ) {
ans = w . clone ();
}
}
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
35
36
37
38
39
40
41
42
43
44
45
46
47 public class Trie {
private Trie [] children = new Trie [ 26 ];
private bool isEnd ;
public Trie () { }
public void Insert ( string w ) {
Trie node = this ;
foreach ( char c in w . ToCharArray ()) {
int idx = c - 'a' ;
if ( node . children [ idx ] == null ) {
node . children [ idx ] = new Trie ();
}
node = node . children [ idx ];
}
node . isEnd = true ;
}
public bool Search ( string w ) {
Trie node = this ;
foreach ( char c in w . ToCharArray ()) {
int idx = c - 'a' ;
node = node . children [ idx ];
if ( ! node . isEnd ) {
return false ;
}
}
return true ;
}
}
public class Solution {
public string LongestWord ( string [] words ) {
Trie trie = new Trie ();
foreach ( string w in words ) {
trie . Insert ( w );
}
string ans = "" ;
foreach ( string w in words ) {
if (( w . Length > ans . Length || ( w . Length == ans . Length && string . Compare ( w , ans ) < 0 )) && trie . Search ( w )) {
ans = w ;
}
}
return ans ;
}
}
GitHub