Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Word Break

LeetCode #139Medium
dp[i] = can s[0..i) be split into dictionary words

Given a string and a dictionary of words, determine whether the string can be segmented into a sequence of one or more dictionary words. Words may be reused.

Asked atAmazonGoogleMetaBloomberg
step 1 / 12
l
e
e
t
c
o
d
e
[0][1][2][3][4][5][6][7]
dp
·
·
·
·
·
·
·
·
·
[0][1][2][3][4][5][6][7][8]
DP over prefixes
▸
1def wordBreak(s, words):
2    dict = set(words)
3    dp = [False] * (n + 1)
4    dp[0] = True                  # empty prefix
5    for i in 1..n:
6        for j in 0..i−1:
7            # prefix splittable AND suffix is a word
8            if dp[j] and s[j:i] in dict:
9                dp[i] = True
10                break
11    return dp[n]
state
  • s"leetcode"
  • dict{leet, code}

line 1Word Break: can "leetcode" be cut into a sequence of dictionary words? Dictionary = {"leet", "code"}. Top row is the letters; the dp row (length n+1) marks which prefixes are fully splittable.