LeetCode OJ:Word Break II

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

算法思想:

用dp[i][j]保存从i到j是否在字典中存在,然后根据dp递归将字符串构造出来

思想比较简单,但是需要注意一点:如果从前至后递归构造字符串,比如我第一次写的递归代码

void dfs(int k, string &s){ if(k==length){ string str; for(int i=0;i
提交上去最后一条测试数据总是超时,所以我们得从后向前递归,减少递归次数

void dfs(int k, string &s){ if(k==-1){ string str; for(int i=t.size()-1;i>=0;i--){ str += t[i]; if(i!=0) str.push_back(' '); } result.push_back(str); return; } for(int i=0;iAC的代码如下:

class Solution{ public: vector result; vector> dp; vector t; int length; void dfs(int k, string &s){ if(k==-1){ string str; for(int i=t.size()-1;i>=0;i--){ str += t[i]; if(i!=0) str.push_back(' '); } result.push_back(str); return; } for(int i=0;i wordBreak(string s, unordered_set &dict) { length=s.size(); dp.resize(length); for(int i=0;i

点击复制链接 与好友分享!回本站首页
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
上一篇:HDU 1474 HDU1580 UVA570 Always On the Run
下一篇:C++空类中的默认函数
相关文章

LeetCode题目9 Count and Say

[LeetCode] Best Time to Buy an

[leetcode]Implement strStr()

leetcode代码分类汇总之-树

[LeetCode]Convert Sorted Array t

[LeetCode]Container With Most Water

[LeetCode]Construct Binary Tree

[LeetCode]Construct Binary Tree

[LeetCode]Merge Sorted Array

[LeetCode]Merge k Sorted Lists

图文推荐
LeetCode OJ:Word Break II
ZOJ 3640 Help Me
LeetCode OJ:Word Break II
CF 518C(Anya and
LeetCode OJ:Word Break II
hdu 1016 Prime R
UVA - 11987 - A

分类:默认分类 时间:2013-04-18 人气:3
本文关键词:
分享到:

相关文章

  • Leetcode dfs Word Break II 2013-07-08

    Word Break II Total Accepted: 15138 Total Submissions: 92228My Submissions 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 ex

  • Leetcode dp Word Break 2014-06-04

    Word Break Total Accepted: 22281 Total Submissions: 105657My Submissions 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 = "leetcod

  • DP32 单词按照字典分割问题 Word Break Problem @geeksforgeeks 2015-02-04

    Given an input string and a dictionary of words, find out if the input string can be segmented into a space-separated sequence of dictionary words. See following examples for more details. This is a famous Google interview question, also being asked

  • Leetcode--Word Break 2013-04-17

    Problem Description: 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 "le

  • LeetCode | Word Break II 2013-07-15

    题目 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", "do

  • [LeetCode] [动态规划] Word Break 2014-05-03

    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 segmen

  • LeetCode | Reverse Words in a String 2014-01-11

    题目 Given an input string, reverse the string word by word. For example, Given s = "the sky is blue", return "blue is sky the". click to show clarification. Clarification: What constitutes a word? A sequence of non-space characters constitutes a word.

  • Linked List Cycle [leetcode] 2012-11-06

    Given a linked list, determine if it has a cycle in it. #include #include #include using namespace std; struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; class Solution { public: bool hasCycle(ListNode *head) { Lis

  • HDU 1561 The more, The Better / 树形DP 2012-02-27

    树形DP 选m个节点权值加起来最大 因为可能是森林 就是都没有限制就可以选 去一个超级源点0 这样就是一棵树了 然后就是基础的树形DP了 DP方程很好想 也很好转移 #include #include #include using namespace std; const int maxn = 210; struct node { int v, w; }; vector G[maxn]; int n, m; int dp[maxn][maxn]; int a[maxn]; int sum[max

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.032 (s). 10 q(s)