题目描述

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

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

示例 1：

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

具体见题目详解。

算法思路

这道题目我直接用dfs写的，结果超时了，因为我是正向dfs搜索的，如果遇到字符串 s = "aaa...aaaaa"，worddict={a, aa, aaa, aaa...aaaa}时就很麻烦，明明直接匹配最长的进行搜索就可以，但是正向搜导致其每次只会搜到一个’a’。但是我以为是搜索直接过不了，就没继续写了，但是当我提交完成后看到有人用深搜过了是感觉有点黑暗。我们直接看看官方题解，给的思路是动态规划。我大致总结了一下，思路如下：

  1. 我们计dp[i]为s[0~i]是否可以由wordDict中的单词组合而成，很显然，我们可以遍历0~i，记中间点为j，如果dp[j]=1并且s[j+1 ~ n]可以在wordDict中找到，那么就说明dp[i]应该也是 true。
  2. 依次遍历 i = 1, 2, ..., n，求出状态数组，最终的dp[n]就是答案

可以看一下代码，很容易理解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        auto wordDictSet = unordered_set <string> ();
        for (auto word: wordDict) {
            wordDictSet.insert(word);
        }

        auto dp = vector <bool> (s.size() + 1);
        dp[0] = true;
        for (int i = 1; i <= s.size(); ++i) {
            for (int j = 0; j < i; ++j) {
                if (dp[j] && wordDictSet.find(s.substr(j, i - j)) != wordDictSet.end()) {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[s.size()];
    }
};

只不过确实很难想出来，我估计面试能dfs出来就不错了……