给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

原文

这个题应该就是递归回溯，解法代码如下，但是有一种场景会超时

这个方法会超时，最主要的问题是 最后一个用例，其实wordDict里面 a aa aaa ... 都可以简化为a，就不会超时，打log分析了一下如果只有a，递归的数量级差距非常大

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function (s, wordDict) {
    let result = false;
    let slen = s.length;
    const helper = (position) => {
        if (result) {
            return;
        }
        if (position === slen) {
            result = true;
            return;
        }
        for (let i = 0; i < wordDict.length; i++) {
            if (match(s, position, wordDict[i])) {
                let length = wordDict[i].length
                position += length;
                helper(position);
                position -= length;
            }
        }
    };
    helper(0);
    return result;
};

const match = (s, position, word) => {
    let match = true;
    for (let i = 0; i < word.length; i++) {
        if (s[i + position] !== word[i]) {
            match = false;
            break;
        }
    }
    return match;
};