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

链接

耗时

解题：4 h 10 min

题意

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。

说明：

• 分隔时可以重复使用字典中的单词。
• 你可以假设字典中没有重复的单词。

思路

DP 求解的数量（可能的句子的数量），并记录解在字典中的位置，然后回溯找到每个解。

DP： sum[i] 表示对于字符串 s[0:i] 的解的数量。对于字典中的每个单词来说都可能匹配到，所以判断 s[i-wordlen+1:i] 是否和 当前单词 一样。即把问题分成两段 [0:i-wordlen] 和 [i-wordlen+1:i]，第一段看 s[0:i-wordlen] 的解的数量即 sum[i-wordlen] 的值是否大于 0，第二段看 s[i-wordlen+1:i] 是否和 当前单词 一样。如果都成立，说明当前子问题 s[0:i] 有 sum[i-wordlen] 个解。对于边界情况，即 i-woedlen+1 = 0，说明当前子问题 s[0:i] 有 1 个解。并在过程中记录所有 s[i-wordlen+1:i] 和 字典中单词一样的单词的位置。

回溯： 从字符串 s 的最后一个位置开始，根据之前记录的单词位置向前回溯，每次将单词加入路径向量，处理完再删除。当到达 -1 的位置时，反向将路径向量中的单词组成句子 加入 结果。

时间复杂度：$O(n\ast m)$

AC代码

class Solution {   private:    vector
   
     wordDict;    vector
    
     
      > wordDictmatchpos;    vector
      
        ans;public:    void dfs(int row, vector
       
         path) {           if(row < 0) {               string tmp;            for(int i = path.size()-1; i >= 0; --i) {                   tmp += path[i];                if(i != 0) tmp += " ";            }            ans.push_back(tmp);            return ;        }        for(auto j : wordDictmatchpos[row]) {               path.push_back(wordDict[j]);            dfs(row-wordDict[j].size(), path);            path.pop_back();        }           }    vector
        
          wordBreak(string s, vector
         
          & wordDict) { this->wordDict = wordDict; int n = s.size(); int m = wordDict.size(); // letter check vector
          
            s_letter(300, 0); vector
           
             wordDict_letter(300, 0); for(auto c : s) { s_letter[c] = 1; } for(auto word : wordDict) { for(auto c : word) { wordDict_letter[c] = 1; } } for(int i = 0; i < 300; ++i) { if(s_letter[i] == 1 && wordDict_letter[i] == 0) { return { }; } } // 1. count wordDictmatchpos.resize(n); vector
            
              sum(n, 0); for(int i = 0; i < n; ++i) { for(int j = 0; j < m; ++j) { int wordlen = wordDict[j].size(); if(i < wordlen-1) continue; string ss = s.substr(i-wordlen+1, wordlen); if(ss == wordDict[j]) { if(i-wordlen >= 0 && sum[i-wordlen] > 0) { sum[i] += sum[i-wordlen]; } else if(i-wordlen < 0) { sum[i]++; } wordDictmatchpos[i].push_back(j); } } } // 1. count end // 2. Back Tracking if(sum[n-1] > 0) { dfs(n-1, { }); } // 2. Back Tracking end return ans; }};