Java 9m Solution with Simple DP

  • 0
    public class Solution {
        public boolean wordBreak(String s, Set<String> wordDict) {
            boolean[] dp = new boolean[s.length()+1];
            dp[0] = true;
            for(int i = 0; i <s.length();i++){
                String sub = s.substring(0,i+1);
                    dp[i+1] = true; //if dictionary has substring, it is a valid partition. 
                    for(int j = sub.length()-1;j>=0;j--){ // if dictionary hasn't substring, we need to figure out whether there exists further partition in substring. We use another pointer j to iterate.
                            if(dp[j+1]){ // if substring has a correct partition, check whether the string front of partition point is in the dictionary.
                                dp[i+1] = true; // a valid internal partition means both two substrings are in the dictionary.
            return dp[s.length()];

Log in to reply

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