139. Word Break

  • 28.9%

https://leetcode.com/problems/word-break/

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

1
2
3
4
5
For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

UPDATE (2017/1/4):

The wordDict parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.


方法一:

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
int n = s.size();
if(n==0) return true;
vector<bool> dp(n+1, false);
dp[0] = true;
// vector to unordered_set的用法,重点学习一下
unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
for(int i=1; i<=n; i++){
for(int j=i-1; j>=0; j--){
if(dp[j]){
string word = s.substr(j, i-j);
if(wordSet.find(word)!=wordSet.end()){
dp[i] = true;
break;
}
}
}
}
return dp[n];
}
};

https://discuss.leetcode.com/topic/7299/c-dynamic-programming-simple-and-fast-solution-4ms-with-optimization

6ms, September 9, 2016

C++ Dynamic Programming simple and fast solution (4ms) with optimization

We use a boolean vector dp[]. dp[i] is set to true if a valid word (word sequence) ends there. The optimization is to look from current position i back and only substring and do dictionary look up in case the preceding position j with dp[j] == true is found.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
bool wordBreak(string s, unordered_set<string>& wordDict) {
if(wordDict.size()==0) return false;

vector<bool> dp(s.size()+1, false);
dp[0]=true;

for(int i=1; i<=s.size(); i++){
for(int j=i-1; j>=0; j--){
if(dp[j]){
string word = s.substr(j, i-j);
if(wordDict.find(word)!=wordDict.end()){
dp[i] = true;
break;
}
}
}
}
return dp[s.size()];
}
};

https://discuss.leetcode.com/topic/2545/a-solution-using-bfs

A solution using BFS

People have posted elegant solutions using DP. The solution I post below using BFS is no better than those. Just to share some new thoughts.

We can use a graph to represent the possible solutions. The vertices of the graph are simply the positions of the first characters of the words and each edge actually represents a word. For example, the input string is “nightmare”, there are two ways to break it, “night mare” and “nightmare”. The graph would be

0–>5–>9

| _^

The question is simply to check if there is a path from 0 to 9. The most efficient way is traversing the graph using BFS with the help of a queue and a hash set. The hash set is used to keep track of the visited nodes to avoid repeating the same work.

For this problem, the time complexity is O(n^2) and space complexity is O(n), the same with DP. This idea can be used to solve the problem word break II. We can simple construct the graph using BFS, save it into a map and then find all the paths using DFS.

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
bool wordBreak(string s, unordered_set<string> &dict) {
// BFS
queue<int> BFS;
unordered_set<int> visited;

BFS.push(0);
while(BFS.size() > 0)
{
int start = BFS.front();
BFS.pop();
if(visited.find(start) == visited.end())
{
visited.insert(start);
for(int j=start; j<s.size(); j++)
{
string word(s, start, j-start+1);
if(dict.find(word) != dict.end())
{
BFS.push(j+1);
if(j+1 == s.size())
return true;
}
}
}
}

return false;
}

python


https://discuss.leetcode.com/topic/8109/simple-dp-solution-in-python-with-description

Simple DP solution in Python with description

75ms, 18.48%, September 7, 2016

The idea is the following:

  • d is an array that contains booleans
  • d[i] is True if there is a word in the dictionary that ends at ith index of s AND d is also True at the beginning of the word

Example:

  • s = “leetcode”
  • words = [“leet”, “code”]
  • d[3] is True because there is “leet” in the dictionary that ends at 3rd index of “leetcode”
  • d[7] is True because there is “code” in the dictionary that ends at the 7th index of “leetcode” AND d[3] is True

The result is the last index of d.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: Set[str]
:rtype: bool
"""
d = [False] * len(s)
for i in range(len(s)):
for w in wordDict:
if w == s[i-len(w)+1:i+1] and (d[i-len(w)] or i-len(w) == -1):
d[i] = True
return d[-1]


https://discuss.leetcode.com/topic/16701/4-lines-in-python

4 lines in Python

ok[i] tells whether s[:i] can be built.

1
2
3
4
5
def wordBreak(self, s, words):
ok = [True]
for i in range(1, len(s)+1):
ok += any(ok[j] and s[j:i] in words for j in range(i)),
return ok[-1]

java


https://discuss.leetcode.com/topic/6156/java-implementation-using-dp-in-two-ways

12ms, September 9, 2016

Java implementation using DP in two ways

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
public class Solution {
public boolean wordBreak(String s, Set<String> dict) {

boolean[] f = new boolean[s.length() + 1];

f[0] = true;


/* First DP
for(int i = 1; i <= s.length(); i++){
for(String str: dict){
if(str.length() <= i){
if(f[i - str.length()]){
if(s.substring(i-str.length(), i).equals(str)){
f[i] = true;
break;
}
}
}
}
}*/

//Second DP
for(int i=1; i <= s.length(); i++){
for(int j=0; j < i; j++){
if(f[j] && dict.contains(s.substring(j, i))){
f[i] = true;
break;
}
}
}

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

https://discuss.leetcode.com/topic/9615/dfs-with-path-memorizing-java-solution

DFS with Path Memorizing Java Solution

I write this method by what I learned from @mahdy in his post Decode Ways

Use a set to record all position that cannot find a match in dict. That cuts down the run time of DFS to O(n^2)

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
public class Solution {
public boolean wordBreak(String s, Set<String> dict) {
// DFS
Set<Integer> set = new HashSet<Integer>();
return dfs(s, 0, dict, set);
}

private boolean dfs(String s, int index, Set<String> dict, Set<Integer> set){
// base case
if(index == s.length()) return true;
// check memory
if(set.contains(index)) return false;
// recursion
for(int i = index+1;i <= s.length();i++){
String t = s.substring(index, i);
if(dict.contains(t))
if(dfs(s, i, dict, set))
return true;
else
set.add(i);
}
set.add(index);
return false;
}
}
谢谢你,可爱的朋友。