题目描述

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

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

输入输出示例及数据范围

思路

这道题的思路其实和 LeetCode 322. 兑换零钱 是差不多的。先来说这道题目，我们的目标是判断能否根据给定的字符串数组当中的字符串拼接出目标字符串，且字典中的串可以重复使用，实际上要做的就是判断目标串当中每一个下标位置对应的子串能否和字典中的某个串匹配。如果s[i + 1... j]与字典中的某个串wordDict[k]匹配，并且s[0... i]已经明确可以由wordDict当中的串拼接组成，那么s[0... j]当然也就可以通过wordDict当中的串拼接而成。

至此，思路已经非常清晰了，我们需要一个 bool 类型的 dp 数组，用来存储目标串每个位置对应的从头开始到i的子串s[0... i]是否可以由字典wordDict当中的串拼接而成，当然有dp[0] = true。

之后，枚举s的每一个下标i，并在枚举i的循环中嵌套一个枚举wordDict的循环，令len = wordDict[k].size()，如果i >= len，可以进一步判断dp[i - len]是否为 true，如果为 true 说明 i - len 之前的串可以通过字典中的串拼接而成，再判断当前s[i - len... i]这部分的串能否和字典中的串，如果可以，那么dp[i] = true，代表s[0... i]可以由字典中的串拼接组成。

最后返回dp[n]得到答案。

C++ 实现

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {int n = s.size();vector<bool> dp(n + 1, false);dp[0] = true;for(int i=1; i<=n; i++) {for(auto &str: wordDict) {int len = str.size();if(i >= len && dp[i - len] && s.substr(i - len, len) == str) {dp[i] = true;}}}return dp[n];}
};