Trie
Memoization
Array
Hash Table
String
Dynamic Programming
Description
Given a string s
and a dictionary of strings wordDict
, return true
if s
can be segmented into a space-separated sequence of one or more dictionary words.
Note that the same word in the dictionary may be reused multiple times in the segmentation.
Example 1:
Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".
Example 2:
Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.
Example 3:
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false
Constraints:
1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s
and wordDict[i]
consist of only lowercase English letters.
All the strings of wordDict
are unique .
Solutions
Solution 1
Python3 Java C++ Go TypeScript Rust C#
class Solution :
def wordBreak ( self , s : str , wordDict : List [ str ]) -> bool :
words = set ( wordDict )
n = len ( s )
f = [ True ] + [ False ] * n
for i in range ( 1 , n + 1 ):
f [ i ] = any ( f [ j ] and s [ j : i ] in words for j in range ( i ))
return f [ n ]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 class Solution {
public boolean wordBreak ( String s , List < String > wordDict ) {
Set < String > words = new HashSet <> ( wordDict );
int n = s . length ();
boolean [] f = new boolean [ n + 1 ] ;
f [ 0 ] = true ;
for ( int i = 1 ; i <= n ; ++ i ) {
for ( int j = 0 ; j < i ; ++ j ) {
if ( f [ j ] && words . contains ( s . substring ( j , i ))) {
f [ i ] = true ;
break ;
}
}
}
return f [ n ] ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 class Solution {
public :
bool wordBreak ( string s , vector < string >& wordDict ) {
unordered_set < string > words ( wordDict . begin (), wordDict . end ());
int n = s . size ();
bool f [ n + 1 ];
memset ( f , false , sizeof ( f ));
f [ 0 ] = true ;
for ( int i = 1 ; i <= n ; ++ i ) {
for ( int j = 0 ; j < i ; ++ j ) {
if ( f [ j ] && words . count ( s . substr ( j , i - j ))) {
f [ i ] = true ;
break ;
}
}
}
return f [ n ];
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 func wordBreak ( s string , wordDict [] string ) bool {
words := map [ string ] bool {}
for _ , w := range wordDict {
words [ w ] = true
}
n := len ( s )
f := make ([] bool , n + 1 )
f [ 0 ] = true
for i := 1 ; i <= n ; i ++ {
for j := 0 ; j < i ; j ++ {
if f [ j ] && words [ s [ j : i ]] {
f [ i ] = true
break
}
}
}
return f [ n ]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 function wordBreak ( s : string , wordDict : string []) : boolean {
const words = new Set ( wordDict );
const n = s . length ;
const f : boolean [] = new Array ( n + 1 ). fill ( false );
f [ 0 ] = true ;
for ( let i = 1 ; i <= n ; ++ i ) {
for ( let j = 0 ; j < i ; ++ j ) {
if ( f [ j ] && words . has ( s . substring ( j , i ))) {
f [ i ] = true ;
break ;
}
}
}
return f [ n ];
}
1
2
3
4
5
6
7
8
9
10
11
12
13 impl Solution {
pub fn word_break ( s : String , word_dict : Vec < String > ) -> bool {
let words : std :: collections :: HashSet < String > = word_dict . into_iter (). collect ();
let mut f = vec! [ false ; s . len () + 1 ];
f [ 0 ] = true ;
for i in 1 ..= s . len () {
for j in 0 .. i {
f [ i ] |= f [ j ] && words . contains ( & s [ j .. i ]);
}
}
f [ s . len ()]
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 public class Solution {
public bool WordBreak ( string s , IList < string > wordDict ) {
var words = new HashSet < string > ( wordDict );
int n = s . Length ;
var f = new bool [ n + 1 ];
f [ 0 ] = true ;
for ( int i = 1 ; i <= n ; ++ i ) {
for ( int j = 0 ; j < i ; ++ j ) {
if ( f [ j ] && words . Contains ( s . Substring ( j , i - j ))) {
f [ i ] = true ;
break ;
}
}
}
return f [ n ];
}
}
Solution 2
Python3 Java C++ Go TypeScript 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 class Trie :
def __init__ ( self ):
self . children : List [ Trie | None ] = [ None ] * 26
self . isEnd = False
def insert ( self , w : str ):
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 . isEnd = True
class Solution :
def wordBreak ( self , s : str , wordDict : List [ str ]) -> bool :
trie = Trie ()
for w in wordDict :
trie . insert ( w )
n = len ( s )
f = [ False ] * ( n + 1 )
f [ n ] = True
for i in range ( n - 1 , - 1 , - 1 ):
node = trie
for j in range ( i , n ):
idx = ord ( s [ j ]) - ord ( 'a' )
if not node . children [ idx ]:
break
node = node . children [ idx ]
if node . isEnd and f [ j + 1 ]:
f [ i ] = True
break
return f [ 0 ]
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 class Solution {
public boolean wordBreak ( String s , List < String > wordDict ) {
Trie trie = new Trie ();
for ( String w : wordDict ) {
trie . insert ( w );
}
int n = s . length ();
boolean [] f = new boolean [ n + 1 ] ;
f [ n ] = true ;
for ( int i = n - 1 ; i >= 0 ; -- i ) {
Trie node = trie ;
for ( int j = i ; j < n ; ++ j ) {
int k = s . charAt ( j ) - 'a' ;
if ( node . children [ k ] == null ) {
break ;
}
node = node . children [ k ] ;
if ( node . isEnd && f [ j + 1 ] ) {
f [ i ] = true ;
break ;
}
}
}
return f [ 0 ] ;
}
}
class Trie {
Trie [] children = new Trie [ 26 ] ;
boolean isEnd = false ;
public void insert ( String w ) {
Trie node = this ;
for ( int i = 0 ; i < w . length (); ++ i ) {
int j = w . charAt ( i ) - 'a' ;
if ( node . children [ j ] == null ) {
node . children [ j ] = new Trie ();
}
node = node . children [ j ] ;
}
node . isEnd = true ;
}
}
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 class Trie {
public :
vector < Trie *> children ;
bool isEnd ;
Trie ()
: children ( 26 )
, isEnd ( false ) {}
void insert ( string word ) {
Trie * node = this ;
for ( char c : word ) {
c -= 'a' ;
if ( ! node -> children [ c ]) node -> children [ c ] = new Trie ();
node = node -> children [ c ];
}
node -> isEnd = true ;
}
};
class Solution {
public :
bool wordBreak ( string s , vector < string >& wordDict ) {
Trie trie ;
for ( auto & w : wordDict ) {
trie . insert ( w );
}
int n = s . size ();
vector < bool > f ( n + 1 );
f [ n ] = true ;
for ( int i = n - 1 ; ~ i ; -- i ) {
Trie * node = & trie ;
for ( int j = i ; j < n ; ++ j ) {
int k = s [ j ] - 'a' ;
if ( ! node -> children [ k ]) {
break ;
}
node = node -> children [ k ];
if ( node -> isEnd && f [ j + 1 ]) {
f [ i ] = true ;
break ;
}
}
}
return f [ 0 ];
}
};
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 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 {
c -= 'a'
if node . children [ c ] == nil {
node . children [ c ] = newTrie ()
}
node = node . children [ c ]
}
node . isEnd = true
}
func wordBreak ( s string , wordDict [] string ) bool {
trie := newTrie ()
for _ , w := range wordDict {
trie . insert ( w )
}
n := len ( s )
f := make ([] bool , n + 1 )
f [ n ] = true
for i := n - 1 ; i >= 0 ; i -- {
node := trie
for j := i ; j < n ; j ++ {
k := s [ j ] - 'a'
if node . children [ k ] == nil {
break
}
node = node . children [ k ]
if node . isEnd && f [ j + 1 ] {
f [ i ] = true
break
}
}
}
return f [ 0 ]
}
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 function wordBreak ( s : string , wordDict : string []) : boolean {
const trie = new Trie ();
for ( const w of wordDict ) {
trie . insert ( w );
}
const n = s . length ;
const f : boolean [] = new Array ( n + 1 ). fill ( false );
f [ n ] = true ;
for ( let i = n - 1 ; i >= 0 ; -- i ) {
let node : Trie = trie ;
for ( let j = i ; j < n ; ++ j ) {
const k = s . charCodeAt ( j ) - 97 ;
if ( ! node . children [ k ]) {
break ;
}
node = node . children [ k ];
if ( node . isEnd && f [ j + 1 ]) {
f [ i ] = true ;
break ;
}
}
}
return f [ 0 ];
}
class Trie {
children : Trie [];
isEnd : boolean ;
constructor () {
this . children = new Array ( 26 );
this . isEnd = false ;
}
insert ( w : string ) : void {
let node : Trie = this ;
for ( const c of w ) {
const i = c . charCodeAt ( 0 ) - 97 ;
if ( ! node . children [ i ]) {
node . children [ i ] = new Trie ();
}
node = node . children [ i ];
}
node . isEnd = true ;
}
}
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 public class Solution {
public bool WordBreak ( string s , IList < string > wordDict ) {
Trie trie = new Trie ();
foreach ( string w in wordDict ) {
trie . Insert ( w );
}
int n = s . Length ;
bool [] f = new bool [ n + 1 ];
f [ n ] = true ;
for ( int i = n - 1 ; i >= 0 ; -- i ) {
Trie node = trie ;
for ( int j = i ; j < n ; ++ j ) {
int k = s [ j ] - 'a' ;
if ( node . Children [ k ] == null ) {
break ;
}
node = node . Children [ k ];
if ( node . IsEnd && f [ j + 1 ]) {
f [ i ] = true ;
break ;
}
}
}
return f [ 0 ];
}
}
class Trie {
public Trie [] Children { get ; set ; }
public bool IsEnd { get ; set ; }
public Trie () {
Children = new Trie [ 26 ];
IsEnd = false ;
}
public void Insert ( string word ) {
Trie node = this ;
foreach ( char c in word ) {
int i = c - 'a' ;
if ( node . Children [ i ] == null ) {
node . Children [ i ] = new Trie ();
}
node = node . Children [ i ];
}
node . IsEnd = true ;
}
}