MockInterview:139. Word Break

Medium

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

• The same word in the dictionary may be reused multiple times in the segmentation.
• You may assume the dictionary does not contain duplicate words.

Example 1:

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
             Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

Solution:
Recusively. consider each prefix and search it in dictionary.If the prefix is present in dictionary, we recur for the rest of the string(suffix). if the recursive call for suffix return true, this function return true, otherwise we try next prefix.

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> set = new HashSet<String>();
        for(String item : wordDict){
            set.add(item);
        }
        return wordBreak(s, set);
    }
    
    public boolean wordBreak(String s, HashSet<String> set){
        if(s.isEmpty()) return true;
        for(int i = 1; i <= s.length(); i++){
            String prefix = s.substring(0,i);
            String suffix = s.substring(i,s.length());
            if(set.contains(prefix) && wordBreak(suffix, set)){
                return true;
            }
        }
        return false;
    }
}

DP:
create the DP table to store the result of subproblem. the value of  dp[i] returns true if str[0....i-1] can be segmented into dictionary words,

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

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // HashSet<String> set = new HashSet<String>();
        // for(String item : wordDict){
        //     set.add(item);
        // }
        return wordBreakDP(s, wordDict);
    }
    
    public boolean wordBreakDP(String s, List<String> wordDict){
        int n = s.length();
        boolean[] dp = new boolean[n+1];
        dp[0] = true;
        
        for(int i = 1; i <= n; i++){
            for(String word: wordDict){
                if(word.length() <= i){
                    if(dp[i - word.length()]){
                        if(s.substring(i - word.length(), i).equals(word)){
                            dp[i] = true;
                            break;
                        }
                    }
                }
            }
        }
        return dp[n];
    }
}