Java another way DP

  • 1

    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)
        boolean [] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 0; i < s.length(); i++) {
            if (!dp[i])
            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.