Word Break
Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.
Note that the same word in the dictionary may be reused multiple times in the segmentation.
public class Solution {
public boolean wordBreak(String s, Set<String> dict) {
boolean[] f = new boolean[s.length() + 1];
f[0] = true;
/* This is an alternative way to solve this problem
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;
}
}
}
}
}*/
//This is the method used in the video below
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()];
}
}Posted by Jamie Meyer 21 days ago