【Leetcode】单词拆分：dfs解法、dp解法

原题链接：139. 单词拆分 - 力扣（LeetCode）

一、dfs+记忆化搜索

我们将题目所给的字典存储在一个全局哈希表中，便于提高查找速度。使用全局变量size记录所给字符串的长度，减少需要传递的参数。

int size = 0;
unordered_set<string> set;
bool wordBreak(string s, vector<string>& wordDict) {
    size = s.size();
    for(auto& str : wordDict){
        set.insert(str);
    }
    return dfs(s, 0);
}

思路：对于一个字符串“applepenapple”，我们可以对其作如下判断。

设置一个下标pos用于作为期望被拼接的字符串的起始下标。

首先我们期望pos=0，长度为s.size()的字符串能够被字典中存在的单词拼接。因此我们需要逐个判断以pos为起点，长度为i的单词是否存在于字典中。如果以pos为起点，长度为i的单词存在于字典中，说明s.substr(pos, i)可以被拼接。接下来，我们需要判断pos + i 为起点，长度为 size - pos的剩余的字符串是否能够被拼接。

到这里我们能够发现判断的过程可以使用递归来解决。只有当s.substr(pos, i) 和 s.substr(pos + i, size - pos)都能够被拼接时，才能说明字符串s能够被字典中的单词正确拼接。

例如：对于字符串s=“applepenapple”，wordDict = ["apple", "pen"]。

首先pos=0。从i=1开始循环，寻找以pos为起点，长度为i的单词是否存在于字典中。当i==5时，s.substr(pos, 5) = “apple"，存在于字典中。此时需要继续判断“penapple”是否能够被拼接，则此时需要更新pos = pos + i，更新以后pos下标对应的字符就是'p'，继续判断以pos为起点，长度为i的单词是否存在于字典中，发现当i==3时，s.substr(pos, i) = “pen"，存在于字典中。此时需要继续判断“apple”是否能够被拼接，答案自然是确定的。此时我们发现该字符串能够由字典中的单词拼接而来，所以返回true。

完整代码如下：但仍有注意事项，请继续往下看。

class Solution {
public:
    int size = 0;
    unordered_set<string> set;
    unordered_map<int, bool> memory;
    bool dfs(string s, int pos)
    {
        // 如果以pos下标为起点的字符串已经被判断过，直接返回结果
        if(memory.find(pos) != memory.end()) return memory[pos];

        // 当起点下标到达字符串末尾时，说明该字符串能够被完整拼接，返回true
        if(pos == size) return true; 

        for(int i = 1; i <= size - pos; i++)
        {
            string temp = s.substr(pos, i);
            if(set.find(temp) != set.end() && dfs(s, pos + i))
            {
                // memory[pos] = true; 可以不记录，因为能被正确拼接直接返回true即可
                return true;
            } 
        }
        // 走到这说明以pos为起点的字符串无法被拼接
        // 存储判断结果
        memory[pos] = false;
           
        return false; // 直接返回false
    }
    bool wordBreak(string s, vector<string>& wordDict) {
        size = s.size();
        // 构造哈希表存储字典中的单词
        for(auto& str : wordDict){
            set.insert(str);
        }
        return dfs(s, 0);
    }
};

 dfs注意事项：

1、递归出口（返回时机）

当起点下标pos到达字符串末尾时，说明该字符串能够被完整拼接，返回true。如果在当前递归层次中无法正确拼接以pos为起点的字符串，则返回false。

2、记忆化搜索

为什么需要记忆化？去除记忆化后，我们查看一下提交结果，发现在

s="aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"，

wordDict= ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"] 的情况下超时了。

我们自行模拟一遍递归过程：

在第一次循环时，当pos = 0, i = 1时，s.substr(pos, i) = “a”，存在于字典中，进而进行递归。在第二层递归中，pos = 1, i = 1 时，s.substr(pos, i) = “a”，存在于字典中，继续进行递归。在第三层递归中，pos = 2, i = 1 时，s.substr(pos, i) = “a”，存在于字典中，继续进行递归。直到遇到字符‘b’时发现其不存于字典中，于是返回false；

在第二次循环时，当pos = 0, i = 2时，s.substr(pos, i) = “aa”，存在于字典中，进而进行递归。在第二层递归中，pos = 2, i = 1 时，s.substr(pos, i) = “a”，存在于字典中，继续进行递归。直到遇到字符‘b’时发现其不存于字典中，于是返回false；

我们发现，在第二次循环进行的递归中，以pos = 2起始位置的字符串在第一次循环中就已经得到结果了。后续所做的就是重复的计算与判断。正因为需要避免大量的重复计算和无意义的递归，所以我们需要使用记忆化的方式记录在该次递归执行前所得到的既定结果。

在本题中我们使用哈希表unordered_map<int, bool> memory来记录，key代表pos，value代表true / false，key + value表示以pos为起点的字符串是否能够被成功拼接。

在使用memory时需要先判断pos是否已经被记录在记忆化容器中，如果容器中包含pos，则代表以pos为起点的字符串是否能够被成功拼接的结果已经在之前的递归中得出并被已被记录，可以直接使用。否则需要在memory中记录以pos为起点的字符串是否能够被成功拼接的结果。

二、动态规划

在处理动态规划类的题目时，我们一定要有一个思想：从部分到整体。能够使用动态规划算法，说明该题目一定可以被拆分成一个个的子问题。

对于本题，我们想求字符s能否被字典中的单词成功拼接，可以将其拆分成如下子问题：设index为字符串的下标，start为起始位置（假设start从1开始，具体由自己设置），end为末尾位置，start <= index <= end我们判断当前字符串能否被字典中的单词成功拼接，即是判断以s[start]为起始，s[index - 1]为结尾的字符串 和 以s[index]为起始，s[end]为结尾是否能够被拼接。

而以s[index]为结尾的字符串是否能够被拼接的结果依然可以被拆分成上述的子问题。

由此，我们设置如下dp数组：dp[i]表示以i为结尾的字符串是否是可以被字典中的单词成功拼接。

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        s = " " + s;//使字符串的下标与dp[i]的下标一一对应
        int n = s.size();
        vector<bool> dp(n, false);
        //dp[i]表示以i为结尾的字符串是否是可以被字典中的单词成功拼接
        dp[0] = true;//空字符串视为能够成功拼接
        unordered_set<string> hash(wordDict.begin(), wordDict.end());
        for(int i = 1; i <= n; i++)
        {
            // dp[i]表示以i为结尾的字符串是否是可以被字典中的单词成功拼接
            // 所以对于0 ~ i，需要判断：
            // 1、以s[0]为起始，s[j - 1]为结尾的字符串 
            // 2、以s[j]为起始，s[i]为结尾的字符串是否能够被拼接。
            for(int j = 1; j <= i; j++)
            {
                if(dp[j - 1] && hash.find(s.substr(j, i - j + 1)) != hash.end()){
                    dp[i] = true;
                    break;
                }else{
                    dp[i] = false; // 可以不需要这一步，因为数组元素初始值设置为false
                }
            }
        }
        return dp[n];
    }
};