public final boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<String>();
        for (String word : wordDict) set.add(word);
        return search(s, set, new HashMap<String, Boolean>());
    }

    private final boolean search(String s, Set<String> wordDict, Map<String, Boolean> cache) {
        if (cache.keySet().contains(s)) return cache.get(s);
        int len = s.length();
        boolean res = false;
        for (int i = 0; i <= len; i++) {
            String pre = s.substring(0, i);
            if (!wordDict.contains(pre)) continue;
            if (search(s.substring(i, len), wordDict, cache) || i == len) {
                res = true;
                break;
            }
        }
        cache.put(s, res);
        return res;
    }

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function (s, wordDict) {
    let wordDictSet = new Set();
    for (let i = 0; i < wordDict.length; i++) wordDictSet.add(wordDict[i]);
    return search(s, wordDictSet, new Map());
};

var search = function (s, wordDict, cache) {
    if (cache.get(s) !== undefined) return cache.get(s);
    let len = s.length, res = false;
    for (let i = 0; i <= len; i++) {
        let pre = s.substring(0, i);
        if (!wordDict.has(pre)) continue
        if (search(s.substring(i, len), wordDict, cache) || i == len) {
            res = true;
            break;
        }
    }
    cache.set(s, res);
    return res;
}