1、前言

2、思路

本题的思路是，规定一个索引 start 从字符串 s 的首位开始，将 s 分为前缀 prefix 和剩余子串。如果 prefix 为单词（即在集合 wordDict 能找到），则以下一个 start 开始继续寻找 s 是否能匹配。

但是因为存在重复计算，比如这样一个用例：s = "aaaaab"，wordDict = ["a", "aa", "aaa"]，开始先用 "a" 查找，到最后一个，"a" 不能匹配 "b"，所以继续下一个循环，然后发现循环跳出，最终返回 false。然后一直函数出栈，然后一直重复匹配，直到 false。这其中包含大量重复的计算。所以需要一个记忆话递归，记录已经遍历的地方。

3、代码

public class Q139_WordBreak {

    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<>(wordDict);
        Boolean[] memo = new Boolean[s.length()];
        return canBreak(0, s, set, memo);
    }

    private boolean canBreak(int start, String s, Set<String> set, Boolean[] memo) {
        if(start == s.length()){
            return true;
        }

        if(memo[start] != null){
            return memo[start];
        }

        for(int i = start + 1; i <= s.length(); i++){
            String prefix = s.substring(start, i);
            if(set.contains(prefix) && canBreak(i, s, set, memo)){
                memo[start] = true;
                return true;
            }
        }

        memo[start] = false;
        return false;
    }


    public static void main(String[] args) {
        String s = "aaaaab";
        List<String> wordDict = new ArrayList<>();
        wordDict.add("a");
        wordDict.add("aa");
        wordDict.add("ab");
        System.out.println(new Q139_WordBreak().wordBreak(s, wordDict));
    }
}