Word Break II

描述

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given

s = "catsanddog",

dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

分析

在上一题的基础上，要返回解本身。

代码

  1. // Word Break II
  2. // 动规，时间复杂度O(n^2)，空间复杂度O(n^2)
  3. class Solution {
  4. public:
  5.     vector<string> wordBreak(string s, unordered_set<string> &dict) {
  6.         // 长度为n的字符串有n+1个隔板
  7.         vector<bool> f(s.length() + 1, false);
  8.         // prev[i][j]为true，表示s[j, i)是一个合法单词，可以从j处切开
  9.         // 第一行未用
  10.         vector<vector<bool> > prev(s.length() + 1, vector<bool>(s.length()));
  11.         f[0] = true;
  12.         for (size_t i = 1; i <= s.length(); ++i) {
  13.             for (int j = i - 1; j >= 0; --j) {
  14.                 if (f[j] && dict.find(s.substr(j, i - j)) != dict.end()) {
  15.                     f[i] = true;
  16.                     prev[i][j] = true;
  17.                 }
  18.             }
  19.         }
  20.         vector<string> result;
  21.         vector<string> path;
  22.         gen_path(s, prev, s.length(), path, result);
  23.         return result;
  25.     }
  26. private:
  27.     // DFS遍历树，生成路径
  28.     void gen_path(const string &s, const vector<vector<bool> > &prev,
  29.             int cur, vector<string> &path, vector<string> &result) {
  30.         if (cur == 0) {
  31.             string tmp;
  32.             for (auto iter = path.crbegin(); iter != path.crend(); ++iter)
  33.                 tmp += *iter + " ";
  34.             tmp.erase(tmp.end() - 1);
  35.             result.push_back(tmp);
  36.         }
  37.         for (size_t i = 0; i < s.size(); ++i) {
  38.             if (prev[cur][i]) {
  39.                 path.push_back(s.substr(i, cur - i));
  40.                 gen_path(s, prev, i, path, result);
  41.                 path.pop_back();
  42.             }
  43.         }
  44.     }
  45. };

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/dp/word-break-ii.html