LeetCode - Word Break

Problem description

description

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
  

Analysis

The first thought is to use backtrack.

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> set = new HashSet<>();
        
        for (String str:wordDict){
            set.add(str);
        }
        
        return backtrack(s, 0, set);
    }
    
    HashSet<Integer> failed = new HashSet<>(); 
    
    boolean backtrack(String s, int start, HashSet<String> set){
        if (start == s.length()){
            return true;
        }
        
        for (int i = start+1; i<= s.length(); i++){
            if (set.contains(s.substring(start, i)) && !failed.contains(i)){
                if (backtrack(s, i, set)){
                    return true;
                }
                else{
                    failed.add(i);
                }
            }
        }
        
        return false;
    }
}

Here’s one point need to remember. The failed part is not added until I got a TLE.

What to improve

• in backtrack, it’s best to add memorization by default.