Java 2ms optimized DP solution.


  • 4
    public boolean wordBreak(String s, Set<String> wordDict) {
        boolean[] dp = new boolean[s.length()+1];
        int maxLen = 0;
        for (String str : wordDict) {
            maxLen = Math.max(maxLen, str.length());
        }
        for(int end = 1;end<s.length()+1;end++){
            if(wordDict.contains(s.substring(0,end))) {
                dp[end] = true;
                continue;
            }
           //Here the starting value of i is optimized from 1 to end-maxLen>1?end-maxLen:1 
           //since the difference between i and end cannot be bigger than the maximum length of string in the dictionary.
           // If it is set to 1, it will waste a lot of time on computing meaningless i values.
            for(int i = end-maxLen>1?end-maxLen:1;i<end;i++){
                if(dp[i]==true&&wordDict.contains(s.substring(i,end))){
                    dp[end] = true;
                    break;
                }
            }
        }
        if(dp[s.length()]) return true;
        else return false;
    }

  • 0

    Shorten @Nakanu code :)
    The thinking is similar to BFS, in which way it looks forward maxLen steps. However, the major difference here is that it looks backward maxLen steps at most and can terminate in advance.

    public boolean wordBreak(String s, Set<String> wordDict) {
            boolean[] dp = new boolean[s.length()+1];
            dp[0] = true;
            int maxLen = 0;
            for (String str : wordDict) maxLen = Math.max(maxLen, str.length());
            
            for(int end = 1; end < s.length()+1; end++) {
    // looks back
                for(int j = end-maxLen > 0? end-maxLen : 0;j < end; 
                    if(dp[i] && wordDict.contains(s.substring(i,end))){
                        dp[end] = true;
                        break;
                    }
                }
            }
            return dp[s.length()];
        }
    

  • 0
    Z

    nice solution! Thx


Log in to reply
 

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