本文共 1745 字，大约阅读时间需要 5 分钟。

动态规划是解决这类分割问题的有效方法。首先，我们创建一个布尔数组 dp，dp[i] 标记前 i 个字符是否可以分割成符合条件的词组。初始化 dp[0] = true，因为空字符串不需要分割。接着，对于每个位置 i（从 1 到 n），检查所有可能的 j 值（从 1 到 i），如果存在一个 j 使得 dp[i-j] 为 true，并且子串 s[i-j:i] 在词典中存在，那么 dp[i] 设为 true。最后返回 dp[n] 的值即可。

动态规划的实现步骤：

这种方法的时间复杂度为 O(n * m)，其中 n 是字符串长度，m 是词典中的最大词长，适用于大部分实际问题。

示例代码：

#include 
   
    #include 
    
     using namespace std;class Solution {public:    bool wordBreak(string s, unordered_set
     
       dict) {        int n = s.length();        if (n == 0) return false;                vector
      
        dp(n + 1, false);        dp[0] = true;  // 空字符串可以分割                int max_word_len = 0;        for (const string& word : dict) {            if (word.length() > max_word_len) {                max_word_len = word.length();            }        }                for (int i = 1; i <= n; ++i) {            for (int j = 1; j <= max_word_len; ++j) {                if (i - j < 0) continue;                if (dp[i - j] && findInDict(s.substr(i - j, j), dict)) {                    dp[i] = true;                    break;                }            }        }                return dp[n];    }        // 辅助函数，检查子串是否在字典中    bool findInDict(const string& substr, const unordered_set
       
        & dict) {        return dict.find(substr) != dict.end();    }};
       
      
     
    
   

优化考虑：

这种方法在处理较长字符串和较大词典时表现优异，是解决此类分割问题的经典方法。