[LeetCode 139] Word Break (Mediu

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

1. 递归求解：对String从左到右顺序扫描，当找到某个substring包含在wordList中，那么递归对后面的substring进行求解。直到扫描完整个String。
2. ！！！！必须用记忆体 Map<String, boolean>： 表示String是否能够在wordList中找到 ，否则遇到String是"aaaaaaaaaaaaaaaaaaaa", ["a", "aa", "aaa"] ，这种case的时候就会出现大量重复，导致超时。
3. 通过Map，在每次进入递归时，先判断currentStr是否在Map中，如果在直接返回其值。如果在wordList中，则加入Map，同时返回true
4. 如果都找不到，就对currentStr开始进行处理。

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        if (wordDict == null || wordDict.size () == 0) {
            return false;
        }
        
        Map<String, Boolean> meme = new HashMap<> ();
        
        return wordBreakHelper (s, wordDict, meme,  0, s.length ()); // start, end
    }
    
    private boolean wordBreakHelper (String str, List<String> wordDict, Map<String, Boolean> meme, int start, int end) {
        if (start  == end) {
            return true;
        }
        
        // 为了防止重复计算，比如 str == "aaaaaaaaaaaaaaaaaaaaaaaaa", ["a", "aa", "aaa"]
        // 如果不加记忆体，那么后面的loop中就会出现大量的重复计算，导致超时
        
        /////////////记忆体///////////////////////
        // 1 如果meme中已有，直接返回其value
        String currentStr = str.substring (start, end);
        if (meme.containsKey (currentStr))
            return meme.get (currentStr);
        
        // 2 如meme中没有，但是wordDict中有，那么表示可以找到，记录入meme，同时返回true
        if (wordDict.contains (currentStr)) {
            meme.put (currentStr, true);
            return true;
        }
            
        // 3. 如果currentStr，没有找到任何匹配，那么就需要继续递归求解
        for (int i = start; i < end; i++) {
            String strCandidate = str.substring (start, i + 1);
                        
            if (wordDict.contains (strCandidate)) {
                // strCandidate在wordList中时，才继续递归求解后面的substring，否则移动startIndex
                if (wordBreakHelper (str, wordDict, meme, i + 1, end)) {
                    meme.put (strCandidate, true);
                    return true;
                }
                    
            } else {
                meme.put (strCandidate, false);
            }
            
        }
        
        // 如果全部扫描了一遍都没有找到，那么返回false
        return false;
    }
}