DP-6. Word Break

Problem

LeetCode 139. Word Break
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:
The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.
Example 1:

Input: s = “leetcode”, wordDict = [“leet”, “code”]
Output: true
Explanation: Return true because “leetcode” can be segmented as “leet code”.

Explanation

Personally speaking, the solution to this problem is similar to Longest Palindromic Substring. As we have to check if the whole string is all contained in the word dictionary. We firstly use pointer i iterate from the 1 to the last character, every time, we use another pointer, j, which iterate from 0 to i, to check if substring(j, i) is contained in the dictionary. If yes, we can move i forward and set dp[i] to true. We can use 1-D array boolean dp[] to represent if substring from the first character ending here are all contained in the word dictionary. So the last value indicates if the whole string is contained.

Solution

Time complexity is O(n^2), as we have to do 2 traversal of the s to fill the dp array.

Space complexity is O(n).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
if (s == null || s.length() == 0) return true;
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;

for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && wordDict.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}

return dp[s.length()];
}
}