Java DP solution


  • 0
    J

    Although memorization can be seen as dp as well, this solution look more like DP :)

        public boolean wordBreak(String s, List<String> wordDict) {
            int len = s.length();
            boolean[][] dp = new boolean[len][len];
            for(int i = 0; i < len; i++) {
                for(int j = 0; i + j < len; j++) {
                    if(wordDict.contains(s.substring(j, i + j + 1))) {
                        dp[j][i + j] = true;
                    } else {
                        for(int k = j; k < i + j; k++) {
                            if(dp[j][k] && dp[k + 1][i + j]) {
                                dp[j][i + j] = true;
                                break;
                            }
                        }
                    }
                }
            }
            return dp[0][len - 1];
        }
    

Log in to reply
 

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