class Solution {
public:
    bool wordBreak(string s, unordered_set<string> &dict) {
        std::vector<bool> dp(s.size() + 1, false);
        dp[0] = true; // 空字符串可以被分割

        for(size_t i = 0;i <= s.size(); i++ ){
            for(size_t j = 0; j <= i;j++){
                if(dp[j] && dict.count(s.substr(j,i-j)) ){
                    dp[i] =true;
                    break;
                }
            }
        }

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

下面是对上述 C++ 代码的详细讲解：

代码结构

  1. 头文件引入iostream：用于输入输出。vector：用于动态数组。unordered_set：用于存储字典中的单词，以便快速查找。string：用于字符串操作。
  2. 主函数 wordBreak参数：s：要检查的字符串。wordDict：存储单词的字典（使用 unordered_set 提高查找效率）。动态规划数组：dp：长度为 s.size() + 1 的布尔数组，用于表示前 i 个字符是否可以分割成字典中的单词。初始化为 false，并将 dp[0] 设置为 true，表示空字符串可以被分割。
  3. 动态规划逻辑外层循环：遍历每个字符的位置 i，从 1 到 s.size()。内层循环：遍历可能的开始位置 j，从 0 到 i-1。 检查子字符串 s[j:i] 是否在字典中，并且 dp[j] 为 true。s.substr(j, i - j) 提取从 j 到 i 的子字符串。如果找到符合条件的 j，则设置 dp[i] 为 true，表示前 i 个字符可以被分割，之后跳出内层循环。
  4. 返回结果返回 dp[s.size()]，这表示整个字符串 s 是否可以被分割。

主函数 main

int main() {
    std::string s = "nowcode";
    std::unordered_set<std::string> wordDict = {"now", "code"};
    
    std::cout << (wordBreak(s, wordDict) ? "true" : "false") << std::endl; // 输出: true
    return 0;
}
  • 字符串 s 和 字典 wordDict 被定义。
  • 调用 wordBreak 函数，并根据返回值输出 "true" 或 "false"。

总结

这段代码通过动态规划有效地解决了字符串分割的问题。时间复杂度为 (O(n^2))，其中 (n) 是字符串的长度，因为每个字符位置都要检查所有可能的起始位置。空间复杂度为 (O(n)) 用于存储 dp 数组。