Several solutions comparison


  • 4
    C
    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;
        }
    }

  • -2

    I tried, but the DFS solution doesn't work


  • 1
    S

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


Log in to reply
 

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