Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Word Break II
Bookmark
Backtracking
DP + Backtracking
Memoization
Input
Multiple solutions
Overlapping words
No solution
Custom
s
=
catsanddog
,
wordDict
=
[cat, cats, and, sand, dog]
s =
"catsanddog"
n =
10
dict
cat
cats
and
sand
dog
s
c
0
a
1
t
2
s
3
a
4
n
5
d
6
d
7
o
8
g
9
memo
sentences
none yet
break "catsanddog" into dictionary words, every possible way
s =
"catsanddog"
n =
10
dict
cat
cats
and
sand
dog
s
c
0
a
1
t
2
s
3
a
4
n
5
d
6
d
7
o
8
g
9
memo
sentences
none yet
break "catsanddog" into dictionary words, every possible way
s =
"catsanddog"
n =
10
dict
cat
cats
and
sand
dog
s
c
0
a
1
t
2
s
3
a
4
n
5
d
6
d
7
o
8
g
9
start 3
memo
sentences of dfs(3)
none yet
dfs(3)
every way to break
"sanddog"
s =
"catsanddog"
n =
10
dict
cat
cats
and
sand
dog
s
c
0
a
1
t
2
s
3
a
4
n
5
d
6
d
7
o
8
g
9
start 7
memo
sentences of dfs(7)
none yet
dfs(7)
every way to break
"dog"
s =
"catsanddog"
n =
10
dict
cat
cats
and
sand
dog
s
c
0
a
1
t
2
s
3
a
4
n
5
d
6
d
7
o
8
g
9
start 10
memo
1
sentences of dfs(10)
""
start = n
whole string consumed, one way: the empty tail
s =
"catsanddog"
n =
10
dict
cat
cats
and
sand
dog
s
c
0
a
1
t
2
s
3
a
4
n
5
d
6
d
7
o
8
g
9
start 3
memo
1
1
sentences of dfs(3)
"sand dog"
s[3..8) =
"sandd"
not a word, extend the window
s =
"catsanddog"
n =
10
dict
cat
cats
and
sand
dog
s
c
0
a
1
t
2
s
3
a
4
n
5
d
6
d
7
o
8
g
9
start 0
memo
1
1
1
sentences of dfs(0)
"cat sand dog"
prefix
"cat"
onto each:
+1
sentence
s =
"catsanddog"
n =
10
dict
cat
cats
and
sand
dog
s
c
0
a
1
t
2
s
3
a
4
n
5
d
6
d
7
o
8
g
9
start 4
memo
1
1
1
sentences of dfs(4)
none yet
s[4..7) =
"and"
is a dictionary word
s =
"catsanddog"
n =
10
dict
cat
cats
and
sand
dog
s
c
0
a
1
t
2
s
3
a
4
n
5
d
6
d
7
o
8
g
9
start 4
memo
1
1
1
sentences of dfs(4)
"and dog"
s[4..9) =
"anddo"
not a word, extend the window
s =
"catsanddog"
n =
10
dict
cat
cats
and
sand
dog
s
c
0
a
1
t
2
s
3
a
4
n
5
d
6
d
7
o
8
g
9
start 0
memo
1
1
1
1
sentences of dfs(0)
"cat sand dog" "cats and dog"
s[0..6) =
"catsan"
not a word, extend the window
s =
"catsanddog"
n =
10
dict
cat
cats
and
sand
dog
s
c
0
a
1
t
2
s
3
a
4
n
5
d
6
d
7
o
8
g
9
memo
2
1
1
1
1
sentences
"cat sand dog" "cats and dog"
2
sentences
algo
master
.
io
Step:
Break "catsanddog" into dictionary words, every possible way
0 / 62
Input
Multiple solutions
Overlapping words
No solution
Custom
s
=
catsanddog
,
wordDict
=
[cat, cats, and, sand, dog]
0 / 62
algo
master
.
io
Step:
Break "catsanddog" into dictionary words, every possible way
