leetcode139：单词拆分

题目链接

leetcode

题目描述

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

C++ 代码

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
#include <algorithm>
using namespace std;

/*
    状态表示：
        f[i] 表示字符串 s[0, i] 是否可以被 wordDict 拼出。
    状态计算：
        对于字符串 s 的每个位置 i，检查所有可能的拆分点 j (0 <= j <= i-1)。
        若 f[j] 为 true，说明字符串 s 的前 j 个字符可以被拆分。
        若 s.substr(j, i-j) 是字典中的单词，则 f[i] = true。

    时间复杂度：O(n^2*m)
        其中 n 是字符串 s 的长度，m 是字典 wordDict 的大小。
        状态计算：O(n^2)，数组中查找的时间复杂度为 O(m)，        
        总的时间复杂度为 O(n^2*m)。
    空间复杂度：O(n)
        数组的大小为 O(n)。
*/
class Solution_0 {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.size();
        vector<bool> f(n+1, false);
        // 初始化
        f[0] = true;

        // 状态计算
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                auto it = find(wordDict.begin(), wordDict.end(), s.substr(j, i-j));
                if (f[j] && wordDict.end() != it) {
                    f[i] = true;
                    break;
                }
            }
        }

        return f[n];
    }
};

/*
    优化时间：unordered_set 存储字典中的单词，
    查找操作的时间复杂度降低到平均 O(1)。

    时间复杂度：O(n^2)
        其中 n 是字符串 s 的长度，m 是字典 wordDict 的大小。
        字典转换为哈希表：O(m)，状态计算：O(n^2)，
        时间复杂度为 O(n^2)。
    空间复杂度：O(n+m)
        数组的大小为 O(n)，哈希表的大小为 O(m)，
        空间复杂度为 O(n+m)。
*/
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> set(wordDict.begin(), wordDict.end());
        int n = s.size();
        vector<bool> f(n+1, false);
        // 初始化
        f[0] = true;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                // if (f[j] && set.find(s.substr(j, i-j)) != set.end()) {
                if (f[j] && set.count(s.substr(j, i - j))) {
                    f[i] = true;
                    break;
                }
            }
        }

        return f[n];
    }
};

// 辅助函数：打印数组
void printArray(const vector<string>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << "\"" << nums[i] << "\"";
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]";
}

int main() {
    Solution solution;
    vector<string> s_cases = {
        "leetcode", "applepenapple", "catsandog"
    };
    vector<vector<string>> wordDict_cases = {
        {"leet", "code"},
        {"apple", "pen"},
        {"cats", "dog", "sand", "and", "cat"}
    };

    for (int i = 0; i < s_cases.size(); i++) {
        string s = s_cases[i];
        vector<string> wordDict = wordDict_cases[i];
        bool result = solution.wordBreak(s, wordDict);

        cout << "Input: s = " << s << ", wordDict = ";
        printArray(wordDict);
        cout << endl;
        cout << "Output: " << (result ? "true" : "false") << endl;
    }

    return 0;
}