# Several solutions comparison

• ``````public class Solution {
//dp without count => 2ms
public boolean wordBreakX(String s, Set<String> wordDict) {
int n = s.length();
boolean [] dp = new boolean [n+1];
dp[0] = true;
for(int i=0;i<n;i++){
for(int j=i;j>=0;j--){
if(!dp[j])continue;  //check this first
if(wordDict.contains(s.substring(j,i+1))){
dp[i+1]=true;
break;  //break!!!!
}
}
}
return dp[n];
}
//dp with count, this will give us how many ways we can break => 11ms
public boolean wordBreak(String s, Set<String> wordDict) {
int n = s.length();
int [] dp = new int [n+1];
dp[0] = 1;
for(int i=0;i<n;i++){
for(int j=i;j>=0;j--){
if(dp[j]==0)continue;
if(wordDict.contains(s.substring(j,i+1))){
dp[i+1]++;
}
}
}
return dp[n]!=0;
}

//simple dfs => TLE
public boolean wordBreakxx(String s, Set<String> wordDict) {
if(s.equals(""))return true;
for(int i=0;i<s.length();i++){
if(wordDict.contains(s.substring(0,i+1))){
if(wordBreak(s.substring(i+1),wordDict))return true;
}
}
return false;
}
}``````

• I tried, but the DFS solution doesn't work

• It's mentioned that DFS returns Time Limit Exceeded, even though it's correct.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.