找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 5331|回复: 17
收起左侧

[米群网刷题小分队] 【LeetCode小分队】【Word Break II 】【刷题第一弹2014】

[复制链接]

11

主题

10

精华

641

积分

超级会员

Rank: 4

积分
641
发表于 10-24-2014 08:51 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
leetcode: https://oj.leetcode.com/problems/word-break-ii/
汇总帖:http://www.meetqun.com/forum.php?mod=viewthread&tid=703
1. 题目:

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"].

2. 分析
动态规划,回溯类题目,
设状态为 f (i),表示 s[0,i] 是否可以分词,则状态转移方程为
f (i) = any_of (f (j )&&s[j + 1; i] 2 dict); 0  j < i
3. 复杂度
时间和空间复杂度均为O(n^2),如果采用DFS,则时间复杂度为O(2^n),超时
4. 代码
  1. class Solution {
  2. public:
  3.     vector<string> wordBreak(string s, unordered_set<string> &dict) {
  4.         vector<bool> f(s.size() + 1);
  5.         vector<vector<bool> > prev = vector<vector<bool> >(s.size() + 1, vector<bool>(s.size(), false));
  6.         f[0] = true;
  7.         for(int i = 1; i <= s.size(); i++){
  8.             for(int j = i - 1; j >= 0; j--){
  9.                 if(f[j] && dict.find(s.substr(j, i - j)) != dict.end()){
  10.                     f[i] = true;
  11.                     prev[i][j] = true;
  12.                 }
  13.             }
  14.         }
  15.         vector<string> path;
  16.         vector<string> result;
  17.         getpath(s, path, result, prev, s.size());
  18.         return result;
  19.     }
  20.    
  21.     void getpath(string s, vector<string> &path, vector<string> &result, vector<vector<bool> > &prev, int cur){
  22.         if(cur == 0){
  23.             string tmp;
  24.             for(int i = path.size() - 1; i >= 0; i++)
  25.                 tmp += path[i] + ' ';
  26.             tmp.erase(tmp.end() - 1);
  27.             result.push_back(tmp);
  28.             return;
  29.         }
  30.         
  31.         for(int i = 0; i < cur; i++){
  32.             if(prev[cur][i]){
  33.                 path.push_back(s.substr(i, cur - i));
  34.                 getpath(s, path, result, prev, i);
  35.                 path.pop_back();
  36.             }
  37.         }
  38.     }
  39. };
复制代码

5. 相关题目:
   Word Break

本帖被以下淘专辑推荐:

23

主题

16

精华

1207

积分

顶级会员

Rank: 6Rank: 6

积分
1207

推广达人宣传达人突出贡献

发表于 10-26-2014 10:36 PM | 显示全部楼层
这题可以写Trie优化一下
回复 支持 反对

使用道具 举报

11

主题

10

精华

641

积分

超级会员

Rank: 4

积分
641
 楼主| 发表于 10-27-2014 03:16 AM | 显示全部楼层
colin 发表于 10-26-2014 10:36 PM
这题可以写Trie优化一下

嗯,ls可以把代码贴出来,渣渣不会呀
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表