[leetcode] 140. Word Break II

[leetcode] 140. Word Break II

Description

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

Note:

The same word in the dictionary may be reused multiple times in the segmentation.You may assume the dictionary does not contain duplicate words.

Example 1:

Input:

s = "catsanddog"wordDict = ["cat", "cats", "and", "sand", "dog"]

Output:

[ "cats and dog", "cat sand dog"]

Example 2:

Input:

s = "pineapplepenapple"wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]

Output:

[ "pine apple pen apple", "pineapple pen apple", "pine applepen apple"]

Explanation:

Note that you are allowed to reuse a dictionary word.

Example 3:

Input:

s = "catsandog"wordDict = ["cats", "dog", "sand", "and", "cat"]

Output:

[]

分析

题目的意思是：给定一个字符串和一个单词字典，把该字符串分成一句子，句子中的每个单词都出现在字典中。

这道题既可以用动态规划的方法，也可以用深度优先的方法。终止条件是遍历到字符串s的末尾。循环体为每次截取一个字串来在字典中查找是否存在，存在则继续递归，不存在则继续循环。

代码

class Solution {public: vector wordBreak(string s, vector& wordDict) { unordered_set dict(wordDict.begin(),wordDict.end()); vector possible(s.size()+1,true); vector ans; string item; dfs(s,0,dict,possible,ans,item); return ans; } bool dfs(string s,int index,unordered_set dict, vector &possible, vector &ans, string item){ bool res=false; if(index==s.size()){ ans.push_back(item.substr(0,item.size()-1)); // remove space in the end return true; } for(int i=index;i

参考文献

​​[编程题]word-break-ii​​​​140. Word Break II​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。