Java solution using DP


  • 22
    A
    public boolean wordBreak(String s, Set<String> wordDict) {
        if (s == null && wordDict == null)
            return true;
        if (s == null || wordDict == null)
            return false;
        //dp[i] represents if s.substring(0, i) is wordbreakable.
        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordDict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }

  • 0
    C

    Great solution! Your code can be optimized a bit. In the inner loop, start from the tail to head instead of head to tail to check if the substring exists. We can break immediately when we see a match.

    We can do even better if we precalculate the min and max of words' lengths in the dictionary. Just need to check from (i-wordLengthMax) to (i-wordLengthMin), and this will yield an algorithm of O(n) instead of O(n^2).

    public class Solution {
        public boolean wordBreak(String s, Set<String> wordDict) {
            if (s == null && wordDict == null)
                return true;
            if (s == null || wordDict == null)
                return false;
            //dp[i] represents if s.substring(0, i+1) is wordbreakable.
            boolean[] dp = new boolean[s.length()+1];
            dp[0] = true;
            for (int i = 1; i <= s.length(); i++) {
                for (int j = i-1; j >=0; j--) {
                    if (dp[j] && wordDict.contains(s.substring(j, i))){
                        dp[i] = true;
                        break;
                    }
                }
            }
            return dp[s.length()];
        }
    }

  • 0
    A

    Thanks for your advices, it is smart! Thanks!
    But I also have following thoughts.

    Basic Assumption: we assume on the characteristics of words in the dictionary.

    (1)I think it is does not matter if j start from 0 or s.length - 1. Let consider following cases,

    s = "abcdef"

    dict1 = {a, b, c, d, e, f}

    dict2 = {a, bcdef}

    For dict1, it is better to scan from tail. But for dict2, it is actually better to scan from front.

    (2)O is the symbol for indicating worst case. Considering following case,

    s = "abcdef"

    dict2 = {a, bcdef}

    If we scan from the tail, we still have O(n^2).

    There may be misunderstanding in my thoughts. Please help me to clarify it and make progress.
    Thanks!


  • 0
    C

    Yeah you are right: ) The code I posted didn't guarantee O(n). But if you only check check from (i-wordLengthMax) to (i-wordLengthMin), it will be O(n), assuming the max length of word is small compare to the input string.


  • 0
    A

    I got your idea. But it could only optimize the algorithm for certain case, let us still consider a worst case.

    s = "abcdefgh"

    doct1 = {abcdefgq, a, b, c, d, e, f, g, h}

    It actually still a O(n^2) solution. I think your idea could squeeze our search space, but we could not say it is O(n) method.

    An way to optimize the code follows your idea is to try every "i - wordLength", where wordLength is the all possible word length in the dict.


  • 0
    C

    Exactly. That's why I was saying that "assuming the max length of word is small compare to the input string".


  • 0
    A

    Got your idea! Thanks!


Log in to reply
 

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