一道很經典的題目，是給定一 string ，能不能分被拆分成 wordDict 裡面的單詞。注意這題，wordDict 裡面的單詞可以重複使用，即單詞使用沒有次數限制，所以 string 可以分成任意段，這就增加了題目的難度。解法蠻多種的，可先從 brute force 下手，再加上暫存優化後，就是蠻標準的 dp 解了，來解一下吧。

思路

從頭開始切 string，如果切到位置可分拆成 wordDict 內的字時，再把剩餘 string再切一次。

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        return find(s, new HashSet<>(wordDict));
    }

    private boolean find(String s, Set<String> set){
        if(set.contains(s)){
            return true;
        }

        for(int i = 0 ; i < s.length() ; i++ ){
            String left = s.substring(0, i);
            String right = s.substring(i);
            if (set.contains(left) && find(right, set)) {
                return true;
            }
        }
        return false;
    }
}

"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"
["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]

是在哪裡導致超時的原因呢 ? 思考一下上述寫法，例如 i = 1 時，切完右邊剩下的 string 若處理完，會發現剛好也處理完成 i = 2 會遇到的 case。但因為是在for loop中呼叫遞迴，故如果沒有把i = 1 時，處理過的 case 儲存下來的話，i = 2 就只能再處理一遍，會因檢查太多次一樣的 substring 導致超時。

解答

class Solution {
    Map<String, Boolean> map = new HashMap<>();

    public boolean wordBreak(String s, List<String> wordDict) {
        return find(s, new HashSet<>(wordDict));
    }

    private boolean find(String s, Set<String> set){
        if (map.containsKey(s)) {
            return map.get(s);
        }

        if(set.contains(s)){
            return true;
        }

        for(int i = 0 ; i < s.length() ; i++ ){
            String left = s.substring(0, i);
            String right = s.substring(i);
            if (set.contains(left) && find(right, set)) {
                return map.compute(s, (k,v) -> true);
            }
        }
         return map.compute(s, (k,v) -> false);
    }
}

map.put(s, true);
return true;

補充

還有一個雙迴圈版本可以看一下，蠻厲害的。