Word Break

描述

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given

s = "leetcode",

dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

分析

设状态为f(i)，表示s[0,i)是否可以分词，则状态转移方程为

f(i) = any_of(f(j) && s[j,i] in dict), 0 <= j < i

深搜

  1. // Word Break
  2. // 深搜，超时
  3. // 时间复杂度O(2^n)，空间复杂度O(n)
  4. class Solution {
  5. public:
  6.     bool wordBreak(string s, unordered_set<string> &dict) {
  7.         return dfs(s, dict, 0, 1);
  8.     }
  9. private:
  10.     static bool dfs(const string &s, unordered_set<string> &dict,
  11.             size_t start, size_t cur) {
  12.         if (cur == s.size()) {
  13.             return dict.find(s.substr(start, cur-start)) != dict.end();
  14.         }
  15.         if (dfs(s, dict, start, cur+1)) return true; // no cut
  16.         if (dict.find(s.substr(start, cur-start)) != dict.end()) // cut here
  17.             if (dfs(s, dict, cur+1, cur+1)) return true;
  18.         return false;
  19.     }
  20. };

动规

  1. // Word Break
  2. // 动规，时间复杂度O(n^2)，空间复杂度O(n)
  3. class Solution {
  4. public:
  5.     bool wordBreak(string s, unordered_set<string> &dict) {
  6.         // 长度为n的字符串有n+1个隔板
  7.         vector<bool> f(s.size() + 1, false);
  8.         f[0] = true; // 空字符串
  9.         for (int i = 1; i <= s.size(); ++i) {
  10.             for (int j = i - 1; j >= 0; --j) {
  11.                 if (f[j] && dict.find(s.substr(j, i - j)) != dict.end()) {
  12.                     f[i] = true;
  13.                     break;
  14.                 }
  15.             }
  16.         }
  17.         return f[s.size()];
  18.     }
  19. };

相关题目

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