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.

For example, given s = “leetcode”, dict = [“leet”, “code”]. Return true because “leetcode” can be segmented as “leet code”.

Solve Word Break Problem in Java

Solution 1:

public class Solution {
public boolean wordBreak(String s, Set<String> dict) {
return wordBreakHelper(s, dict, 0);
}
public boolean wordBreakHelper(String s, Set<String> dict, int start){
if(start == s.length())
return true;
for(String a: dict){
int len = a.length();
int end = start+len;
//end index should be <= string length
if(end > s.length())
continue;
if(s.substring(start, start+len).equals(a))
if(wordBreakHelper(s, dict, start+len))
return true;
}
return false;
}
}

Solution 2:

The key to solve this problem by using dynamic programming approach:
• Define an array t[] such that t[i]==true =>0-(i-1) can be segmented using dictionary
• Initial state t[0] == true

public class Solution {
public boolean wordBreak(String s, Set<String> dict) {
boolean[] t = new boolean[s.length()+1];
t[0] = true; //set first to be true, why?
//Because we need initial state
for(int i=0; i<s.length(); i++){
//should continue from match position
if(!t[i])
continue;
for(String a: dict){
int len = a.length();
int end = i + len;
if(end > s.length())
continue;
if(t[end]) continue;
if(s.substring(i, end).equals(a)){
t[end] = true;
}
}
}
return t[s.length()];
}
}

Time: O(string length * dict size) One tricky part of this solution is the case:

INPUT: “programcreek”, [“programcree”,”program”,”creek”].

We should get all possible matches, not stop at “programcree”.

Solution 3:

Solve Word Break Problem in Java using Regular Expression

The problem is supposed to be equivalent to matching the regexp (leet|code)*, which means that it can be solved by building a DFA in O(2m) and executing it in O(n).

public static void main(String[] args) {
HashSet<String> dict = new HashSet<String>();
dict.add("go");
dict.add("goal");
dict.add("goals");
dict.add("special");
StringBuilder sb = new StringBuilder();
for(String s: dict){
sb.append(s + "|");
}
String pattern = sb.toString().substring(0, sb.length()-1);
pattern = "("+pattern+")*";
Pattern p = Pattern.compile(pattern);
Matcher m = p.matcher("goalspecial");
if(m.matches()){
System.out.println("match");
}
}

Word Break Problem 2 in Java

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

For example, given s = “catsanddog”, dict = [“cat”, “cats”, “and”, “sand”, “dog”], the solution is [“cats and dog”, “cat sand dog”].

public static List<String> wordBreak(String s, Set<String> dict) {
//create an array of ArrayList<String>
List<String> dp[] = new ArrayList[s.length()+1];
dp[0] = new ArrayList<String>();
for(int i=0; i<s.length(); i++){
if( dp[i] == null )
continue;
for(String word:dict){
int len = word.length();
int end = i+len;
if(end > s.length())
continue;
if(s.substring(i,end).equals(word)){
if(dp[end] == null){
dp[end] = new ArrayList<String>();
}
dp[end].add(word);
}
}
}
List<String> result = new LinkedList<String>();
if(dp[s.length()] == null)
return result;

ArrayList<String> temp = new ArrayList<String>();
dfs(dp, s.length(), result, temp);
return result;
}
public static void dfs(List<String> dp[],int end,List<String> result,
ArrayList<String> tmp){
if(end <= 0){
String path = tmp.get(tmp.size()-1);
for(int i=tmp.size()-2; i>=0; i--){
path += " " + tmp.get(i) ;
}
result.add(path);
return;
}
for(String str : dp[end]){
tmp.add(str);
dfs(dp, end-str.length(), result, tmp);
tmp.remove(tmp.size()-1);
}
}