139. Word Break

Medium

这个图很清楚地表达了递归做这个题的方法：
helper method有两种情况可以直接返回值

• 原字符串就在dictionary里面，这时候可以直接返回true, 但要注意记得往memo里面放结果来实现记忆化搜索
• memo里面有该字符是否在字典里的记录，也就是记忆化搜索的优点，不用重复计算

不懂

                //why this following step is necessary???
                memo.put(s, true);
                return true;

这里为什么还必须写memo.put(s, true),直接返回true不行吗？

image.png

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        /*     leetcode    dict:{leet, code}
          wordBreak("l") && inDict("eetcode")
          wordBreak("le") && inDict("etcode")
          wordBreak("lee") && inDict("tcode")
          wordBreak("leet") && inDict("code")
         */
        Set<String> dict = new HashSet<>(wordDict);
        Map<String, Boolean> memo = new HashMap<>();
        return wordBreak(s, dict, memo);
    }
    
    private boolean wordBreak(String s, Set<String> dict, Map<String, Boolean> memo){
        if (dict.contains(s)){
            memo.put(s,true);
            return true;
        }
        
        if (memo.containsKey(s)){
            return memo.get(s);
        }
        
        for (int i = 1; i < s.length(); i++){
            if (wordBreak(s.substring(0, i), dict, memo) && dict.contains(s.substring(i))){
                memo.put(s, true);
                return true;
            } else {
                memo.put(s, false);
            }
        }        
        return false;
    }
}