Word Break

139. 单词拆分

分析

状态定义：
- 定义 f[i]：表示从第 i 个字符到字符串结尾的子串能否被字典中的单词拼接而成
状态转移：
- 对于子串 s[i:j]，若 s[i:j] 出现在字典中，且 f[j] = true，则可以拼接出 s[i:n]，即 f[i] = true
初始化：
- f[n] = true：空字符串可以被成功拼接
结果：
- 返回 f[0]，即判断整个字符串是否可以被拼接

时间复杂度

外层循环遍历字符串 O(n) ，内层循环遍历每个子串的结尾 O(n) ，检查子串是否在字典中平均耗时 O(k) ，其中 k 是子串的平均长度

总时间复杂度为 O(n^2 * k)

空间复杂度

动态规划数组 f 占用 O(n)
哈希表占用 O(l) ，其中 l 是字典中单词的总长度

总空间复杂度为 O(n + l)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


class Solution
{
public:
    bool wordBreak(string s, vector<string>& wordDict)
    {
        std::unordered_set<std::string> hash;  // 使用哈希表存储字典中的单词
        for (std::string word : wordDict)
            hash.insert(word);

        int n = s.size();
        std::vector<bool> f(n + 1, false);  // 动态规划数组
        f[n] = true;  // 初始化空字符串为可拼接

        // 从后向前遍历字符串
        for (int i = n - 1; i >= 0; --i)
        {
            std::string str;  // 记录当前子串
            for (int j = i; j < n; ++j)
            {
                str += s[j];  // 扩展子串
                if (hash.count(str) && f[j + 1])  // 检查是否满足条件
                {
                    f[i] = true;
                    break;
                }
            }
        }

        return f[0];  // 返回结果
    }
};