Java another way DP


  • 1
    M

    Most DP solution tries a position i as the end position, and tries a position j before i, find if dp[j] is true and substring(i, j) is in the dict.

    However I try a position i as the start position, if dp[i], try every word w in dict and set dp[i + w.length()] to true

    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet();
        for (String w : wordDict)
            set.add(w);
        boolean [] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 0; i < s.length(); i++) {
            if (!dp[i])
                continue;
            for (String w : set) {
                if (s.startsWith(w, i))
                    dp[i + w.length()] = true;
            }
        }
        return dp[s.length()];
    }
    

Log in to reply
 

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