企业官网建设流程全解析

题目描述：

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

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

示例 1：

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

示例 2：

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

示例 3：

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

解题思路：

方法一：动态规划

核心思路：

状态定义：

dp[i]= 字符串s的前i个字符能否由字典中的单词拼接而成。

状态转移：

对于每个位置i，枚举j从0到i-1：

• 如果dp[j] == true且s[j..i-1]在字典中

• 则dp[i] = true

dp[i] = dp[j] && wordDict.count(s.substr(j, i-j))

初始化：

dp[0] = true（空字符串可以被拼接）

具体过程示例：

s = "leetcode", wordDict = ["leet", "code"]

dp[0] = true i=1: 检查 s[0..0]="l" → 不在字典 → dp[1]=false i=2: 检查 s[0..1]="le" → 不在字典 → dp[2]=false i=3: 检查 s[0..2]="lee" → 不在字典 → dp[3]=false i=4: 检查 s[0..3]="leet" → 在字典，dp[0]=true → dp[4]=true i=5: 检查 s[0..4]="leetc" → 不在 检查 s[4..4]="c" → 不在 → dp[5]=false i=6: 检查 s[4..5]="co" → 不在 → dp[6]=false i=7: 检查 s[4..6]="cod" → 不在 → dp[7]=false i=8: 检查 s[4..7]="code" → 在字典，dp[4]=true → dp[8]=true ✅

代码实现：

class Solution { public: bool wordBreak(string s, vector<string>& wordDict) { unordered_set<string> dict(wordDict.begin(), wordDict.end()); int n = s.size(); vector<bool> dp(n + 1, false); dp[0] = true; for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { if (dp[j] && dict.count(s.substr(j, i - j))) { dp[i] = true; break; } } } return dp[n]; } };

复杂度分析：

设n是字符串长度，m是字典大小。

更精确：子串s.substr(j, i-j)创建需要 O(L) 时间，所以是 O(n² × L)。

关键细节：

1. 为什么dp[0] = true？

空字符串可以被拼接（什么都不选），是递推的起点。

2. 为什么用unordered_set？

字典需要频繁查找，哈希表查找 O(1)，比遍历数组快。

3. 为什么break？

一旦dp[i] = true，不需要继续枚举j，提前结束内层循环。

4. 和「单词拆分 II」的区别

方法二：记忆化搜索（DFS + 备忘录）

代码实现：

class Solution { public: bool wordBreak(string s, vector<string>& wordDict) { unordered_set<string> dict(wordDict.begin(), wordDict.end()); unordered_map<int, bool> memo; return dfs(s, dict, 0, memo); } private: bool dfs(string& s, unordered_set<string>& dict, int start, unordered_map<int, bool>& memo) { if (start == s.size()) return true; if (memo.count(start)) return memo[start]; for (int end = start + 1; end <= s.size(); end++) { string word = s.substr(start, end - start); if (dict.count(word) && dfs(s, dict, end, memo)) { memo[start] = true; return true; } } memo[start] = false; return false; } };

复杂度：时间 O(n² × L)，空间 O(n)

方法三：BFS

代码实现：

class Solution { public: bool wordBreak(string s, vector<string>& wordDict) { unordered_set<string> dict(wordDict.begin(), wordDict.end()); int n = s.size(); vector<bool> visited(n, false); queue<int> q; q.push(0); while (!q.empty()) { int start = q.front(); q.pop(); if (visited[start]) continue; visited[start] = true; for (int end = start + 1; end <= n; end++) { if (dict.count(s.substr(start, end - start))) { if (end == n) return true; q.push(end); } } } return false; } };

复杂度：时间 O(n² × L)，空间 O(n)

三种方法对比：

总结：