Java 9m Solution with Simple DP


  • 0
    R
    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);
                if(wordDict.contains(sub)){
                    dp[i+1] = true; //if dictionary has substring, it is a valid partition. 
                }else{
                    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(wordDict.contains(sub.substring(j+1))){  
                            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.
                                break;
                            }
                        }
                    }
                }
            }
            return dp[s.length()];
        }
    }
    

Log in to reply
 

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