[数据结构与算法]Leetcode刷题(第139题)——单词拆分

一、题目

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

二、示例

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
注意，你可以重复使用字典中的单词。

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

三、思路
我们使用Set数据结构，保存字典中得全部字符串。然后使用递归。递归传入参数为字符串，如果当前的字符串为"", 则直接返回true,然后在遍历当前字符串，如果字符串前部分在set中，然后对后部分使用递归，如果后部分为true，则直接返回true。如果什么都不存在，则返回false。
四、代码

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function (s, wordDict) {
    let set = new Set(wordDict)
    const rec = (str) => {
        if (str === "") return true
        for(let i = 0; i < str.length; i++) {
            if(set.has(str.substring(0, i + 1))) {
                if(rec(str.substring(i + 1))) {
                    return true
                }
            }
        }
        return false
    }
    return rec(s)
};

上面为代码，但是结果是可以运行出来的，但是会报超时错误。

五、优化
我们要明白，为什么会超时？

例如：如果当前我们输入单词为a(20个)b,然后进行递归，首先递归的是rec(19a + b), 然后是rec(18a + b),......递归到最后。
然后开始递归rec(18a +b), rec(17a +b).....,因为上面都已经递归过了，所以任然需要再次进行计算。才会导致超时。

解决方法：

我们可以使用hash表，如果当前的不存在，则存入hash表中，如果下次我们进行递归时，碰到该字符串，此时直接返回就OK了。

六、优化后的代码

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function (s, wordDict) {
    let set = new Set(wordDict)
    let map = new Map()
    const rec = (str) => {
        if (str === "") return true
        if(map.has(str)) return false
        for(let i = 0; i < str.length; i++) {
            if(set.has(str.substring(0, i + 1))) {
                if(rec(str.substring(i + 1))) {
                    return true
                }else {
                    map.set(str.substring(i + 1), true)
                }
            }
        }
        return false
    }
    return rec(s)
};

七、总结