Trie
Array
Hash Table
String
Description
A valid encoding of an array of words
is any reference string s
and array of indices indices
such that:
words.length == indices.length
The reference string s
ends with the '#'
character.
For each index indices[i]
, the substring of s
starting from indices[i]
and up to (but not including) the next '#'
character is equal to words[i]
.
Given an array of words
, return the length of the shortest reference string s
possible of any valid encoding of words
.
Example 1:
Input: words = ["time", "me", "bell"]
Output: 10
Explanation: A valid encoding would be s = "time#bell#" and indices = [0, 2, 5].
words[0] = "time", the substring of s starting from indices[0] = 0 to the next '#' is underlined in "time #bell#"
words[1] = "me", the substring of s starting from indices[1] = 2 to the next '#' is underlined in "time #bell#"
words[2] = "bell", the substring of s starting from indices[2] = 5 to the next '#' is underlined in "time#bell #"
Example 2:
Input: words = ["t"]
Output: 2
Explanation: A valid encoding would be s = "t#" and indices = [0].
Constraints:
1 <= words.length <= 2000
1 <= words[i].length <= 7
words[i]
consists of only lowercase letters.
Solutions
Solution 1
Python3 Java C++ Go
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 class Trie :
def __init__ ( self ) -> None :
self . children = [ None ] * 26
class Solution :
def minimumLengthEncoding ( self , words : List [ str ]) -> int :
root = Trie ()
for w in words :
cur = root
for c in w [:: - 1 ]:
idx = ord ( c ) - ord ( "a" )
if cur . children [ idx ] == None :
cur . children [ idx ] = Trie ()
cur = cur . children [ idx ]
return self . dfs ( root , 1 )
def dfs ( self , cur : Trie , l : int ) -> int :
isLeaf , ans = True , 0
for i in range ( 26 ):
if cur . children [ i ] != None :
isLeaf = False
ans += self . dfs ( cur . children [ i ], l + 1 )
if isLeaf :
ans += l
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 class Trie {
Trie [] children = new Trie [ 26 ] ;
}
class Solution {
public int minimumLengthEncoding ( String [] words ) {
Trie root = new Trie ();
for ( String w : words ) {
Trie cur = root ;
for ( int i = w . length () - 1 ; i >= 0 ; i -- ) {
int idx = w . charAt ( i ) - 'a' ;
if ( cur . children [ idx ] == null ) {
cur . children [ idx ] = new Trie ();
}
cur = cur . children [ idx ] ;
}
}
return dfs ( root , 1 );
}
private int dfs ( Trie cur , int l ) {
boolean isLeaf = true ;
int ans = 0 ;
for ( int i = 0 ; i < 26 ; i ++ ) {
if ( cur . children [ i ] != null ) {
isLeaf = false ;
ans += dfs ( cur . children [ i ] , l + 1 );
}
}
if ( isLeaf ) {
ans += l ;
}
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 struct Trie {
Trie * children [ 26 ] = { nullptr };
};
class Solution {
public :
int minimumLengthEncoding ( vector < string >& words ) {
auto root = new Trie ();
for ( auto & w : words ) {
auto cur = root ;
for ( int i = w . size () - 1 ; i >= 0 ; -- i ) {
if ( cur -> children [ w [ i ] - 'a' ] == nullptr ) {
cur -> children [ w [ i ] - 'a' ] = new Trie ();
}
cur = cur -> children [ w [ i ] - 'a' ];
}
}
return dfs ( root , 1 );
}
private :
int dfs ( Trie * cur , int l ) {
bool isLeaf = true ;
int ans = 0 ;
for ( int i = 0 ; i < 26 ; ++ i ) {
if ( cur -> children [ i ] != nullptr ) {
isLeaf = false ;
ans += dfs ( cur -> children [ i ], l + 1 );
}
}
if ( isLeaf ) {
ans += l ;
}
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 type trie struct {
children [ 26 ] * trie
}
func minimumLengthEncoding ( words [] string ) int {
root := new ( trie )
for _ , w := range words {
cur := root
for i := len ( w ) - 1 ; i >= 0 ; i -- {
if cur . children [ w [ i ] - 'a' ] == nil {
cur . children [ w [ i ] - 'a' ] = new ( trie )
}
cur = cur . children [ w [ i ] - 'a' ]
}
}
return dfs ( root , 1 )
}
func dfs ( cur * trie , l int ) int {
isLeaf , ans := true , 0
for i := 0 ; i < 26 ; i ++ {
if cur . children [ i ] != nil {
isLeaf = false
ans += dfs ( cur . children [ i ], l + 1 )
}
}
if isLeaf {
ans += l
}
return ans
}
Solution 2
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 class Trie :
def __init__ ( self ):
self . children = [ None ] * 26
def insert ( self , w ):
node = self
pref = True
for c in w :
idx = ord ( c ) - ord ( "a" )
if node . children [ idx ] is None :
node . children [ idx ] = Trie ()
pref = False
node = node . children [ idx ]
return 0 if pref else len ( w ) + 1
class Solution :
def minimumLengthEncoding ( self , words : List [ str ]) -> int :
words . sort ( key = lambda x : - len ( x ))
trie = Trie ()
return sum ( trie . insert ( w [:: - 1 ]) for w in words )
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 class Trie {
Trie [] children = new Trie [ 26 ] ;
int insert ( String w ) {
Trie node = this ;
boolean pref = true ;
for ( int i = w . length () - 1 ; i >= 0 ; -- i ) {
int idx = w . charAt ( i ) - 'a' ;
if ( node . children [ idx ] == null ) {
pref = false ;
node . children [ idx ] = new Trie ();
}
node = node . children [ idx ] ;
}
return pref ? 0 : w . length () + 1 ;
}
}
class Solution {
public int minimumLengthEncoding ( String [] words ) {
Arrays . sort ( words , ( a , b ) -> b . length () - a . length ());
int ans = 0 ;
Trie trie = new Trie ();
for ( String w : words ) {
ans += trie . insert ( 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 class Trie {
public :
vector < Trie *> children ;
Trie ()
: children ( 26 ) {}
int insert ( string w ) {
Trie * node = this ;
bool pref = true ;
for ( char c : w ) {
c -= 'a' ;
if ( ! node -> children [ c ]) {
pref = false ;
node -> children [ c ] = new Trie ();
}
node = node -> children [ c ];
}
return pref ? 0 : w . size () + 1 ;
}
};
class Solution {
public :
int minimumLengthEncoding ( vector < string >& words ) {
sort ( words . begin (), words . end (), []( string & a , string & b ) { return a . size () > b . size (); });
Trie * trie = new Trie ();
int ans = 0 ;
for ( auto & w : words ) {
reverse ( w . begin (), w . end ());
ans += trie -> insert ( 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 type Trie struct {
children [ 26 ] * Trie
}
func newTrie () * Trie {
return & Trie {}
}
func ( this * Trie ) insert ( w string ) int {
node := this
pref := true
for i := len ( w ) - 1 ; i >= 0 ; i -- {
idx := w [ i ] - 'a'
if node . children [ idx ] == nil {
pref = false
node . children [ idx ] = newTrie ()
}
node = node . children [ idx ]
}
if pref {
return 0
}
return len ( w ) + 1
}
func minimumLengthEncoding ( words [] string ) int {
sort . Slice ( words , func ( i , j int ) bool { return len ( words [ i ]) > len ( words [ j ]) })
trie := newTrie ()
ans := 0
for _ , w := range words {
ans += trie . insert ( w )
}
return ans
}
GitHub