Java DP solution with explanation


  • 0
    M
    class Solution {
        public boolean wordBreak(String s, List<String> wordDict) {
            // dp[j] = true if s.substring(0, i) can be segmented
            //       = true if dp[i] == true && s.substring(i, j) is in worDict for any i = 0...j
            Set<String> wordSet = new HashSet<>(wordDict);
            boolean[] dp = new boolean[s.length()+1];
            dp[0] = true;
            for (int j = 1; j <= s.length(); j++) {
                for (int i = 0; i < j; i++) {
                    if (dp[i] && wordSet.contains(s.substring(i, j))) {
                        dp[j] = 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.