My Java DP solution beats 93.83%


  • 11
    B
    public boolean wordBreak(String s, Set<String> wordDict) {
        int maxWord = getMax(wordDict);
        int len = s.length();
        boolean[] dp = new boolean[len + 1];
        dp[0] = true;
        for (int i = 1; i <= len; i ++) {
            int start = Math.max(1, i - maxWord);
            for (int j = start; j <= i; j++) {
                if (dp[j - 1] && wordDict.contains(s.substring(j - 1, i))) {
                    dp[i] = true; 
                    break;
                }
            }
        }
        return dp[len];
    }
    
    private int getMax(Set<String> wordDict) {
        int max = 0;
        for (String str : wordDict) {
            max = Math.max(max, str.length());
        }
        return max;
    }

  • 0
    K

    @biedengle2
    Ah, you are trying to apply some heuristic to always pick try the longest word in the diction as the potential candidate.

    However, for the time complexity wise, I think the time complexity still O(stringlen^2), is that true?


  • 0

    @kun5 Not really, if the strings in wordDict is short (<r) then the running time is r*s.length()


  • 0
    C

    @kun5 unfortunately the time complexity is O(n^3) where n is the word length. because substring takes O(n)


Log in to reply
 

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