首页 > 代码库 > [Leetcode] word break ii拆分词语

[Leetcode] word break ii拆分词语

2024-10-17 00:39:39   215人阅读

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

 题意：找出S用dict表示的各种可能。

思路：这题和Word break的区别是上题中，只要考虑是否在的情况，不用考虑各种组合的问题。参考了GeekFans的。其整体思路是，先使用动态规划，找到字符串S中的各种分类，然后使用DFS找到满足条件的各种情况。代码如下：

 1 class Solution {
 2 private:
 3     vector<string> midress;
 4     vector<string> res;
 5    vector<bool> *dp; 
 6 
 7 public:
 8     vector<string> wordBreak(string s, unordered_set<string> &dict) 
 9     {
10                 
11         int len=s.size();
12 
13         dp=new vector<bool>[len];
14         for(int i=0;i<len;++i)
15         {
16             for(int j=i;j<len;j++)
17             {
18                 if(dict.find(s.substr(i,j-i+1)) !=dict.end())
19                     dp[i].push_back(true);
20                 else
21                     dp[i].push_back(false);
22             }
23         }
24         dfs(s,len-1);
25         return res;
26     }
27 
28     void dfs(const string &s,int i)
29     {
30         if(i>=0)
31         {
32             for(int j=0;j<=i;++j)
33             {
34                 if(dp[j][i-j])
35                 {
36                     midress.push_back(s.substr(j,i-j+1));
37                     dfs(s,j-1);
38                     midress.pop_back();
39                 }
40             }
41             return;
42         }
43         else
44         {
45             string str;
46             for(int k=midress.size()-1;k>=0;--k)
47             {
48                 str+=midress[k];
49                 if(k>0)
50                     str+=" ";
51             }
52             res.push_back(str);
53             return;
54         }
55     }
56 };

 

注：在牛客网通过了，然后一段时间后再次运行时，报错，的结果让我无话可说，见图：

技术分享

网友Grangyang和Code Gander分别给出不错解法。

 

[Leetcode] word break ii拆分词语


联系
我们