【算法与数据结构】139、LeetCode单词拆分

文章目录

一、题目
二、解法
三、完整代码

所有的LeetCode题解索引，可以看这篇文章——【算法和数据结构】LeetCode题解。

一、题目

在这里插入图片描述

二、解法

思路分析：本题可以看做一个动态规划问题。其中，字符串s是背包，而字典中的单词就是物品。题目问的是单词能否组成字符串s，就是问物品能不能把背包装满。字典中的单词可以重复使用，因此是一个完全背包问题。

第一步，
d

p

[

j

]

dp[j]

dp[j]的含义。

d

p

[

j

]

dp[j]

dp[j]代表的是字符串长度为

j

j

j时，该能否由字典中的单词构成。如果能，则为true。
第二步，递推公式。如果确定
d

p

[

j

]

dp[j]

dp[j]是true，且

[

j

,

i

]

[j, i]

[j,i]这个区间的子串出现在字典里，那么

d

p

[

i

]

dp[i]

dp[i]一定是true。

(

j

<

i

)

(j < i )

(j<i)。所以递推公式是：
```
if(dp[j] &&  [j, i]这个区间的子串出现在字典里) dp[i] = true
```
第三部，元素初始化。
d

p

[

0

]

dp[0]

dp[0]初始化为1。
第四部，递归顺序。本题严格划分起来是一个排列问题。以s = “applepenapple”, wordDict = [“apple”, “pen”] 为例。我们要求物品的组合一定是 “apple” + “pen” + “apple” 才能组成 “applepenapple”。“apple” + “apple” + “pen” 或者 “pen” + “apple” + “apple” 是不可以的，那么我们就是强调物品之间顺序。所以说，本题一定是先遍历背包，再遍历物品。
第五步，打印结果。

为了判断

[

j

,

i

]

[j, i]

[j,i]这个区间的子串出现在字典里，我们构建了一个无序集合。其底层实现是一个哈希表，可以在常数时间内（

O

(

1

)

O(1)

O(1)）内进行查找。

程序如下：

class Solution {public:	bool wordBreak(string s, vector& wordDict) {		unordered_set wordSet(wordDict.begin(), wordDict.end());		vector dp(s.size() + 1, 0);		dp[0] = 1;		for (int i = 1; i <= s.size(); i++) {	// 遍历背包（字符串s）			for (int j = 0; j < i; j++) {		// 遍历物品(单词)				string key = s.substr(j, i - j);				if (dp[j] && wordSet.find(key) != wordSet.end()) {					dp[i] = 1;				}			}		}		return dp[s.size()];	}};

复杂度分析：

时间复杂度：
O

(

n

3

)

O(n^3)

O(n3)。除了两层循环以外，还有需要substr返回子串，它是O(n)的复杂度（这里的n是substring的长度）。
空间复杂度：
O

(

n

)

O(n)

O(n)。

三、完整代码

# include # include # include # include using namespace std;class Solution {public:	bool wordBreak(string s, vector& wordDict) {		unordered_set wordSet(wordDict.begin(), wordDict.end());		vector dp(s.size() + 1, 0);		dp[0] = 1;		for (int i = 1; i <= s.size(); i++) {	// 遍历背包（字符串s）			for (int j = 0; j < i; j++) {		// 遍历物品(单词)				string key = s.substr(j, i - j);				if (dp[j] && wordSet.find(key) != wordSet.end()) {					dp[i] = 1;				}			}		}		return dp[s.size()];	}};int main() {	string s = "catsandog";	vector wordDict = { "cats", "dog", "sand", "and", "cat" };	Solution s1;	bool result = s1.wordBreak(s, wordDict);	cout << result << endl;	system("pause"); 	return 0;}

end

本文来自网络，不代表协通编程立场，如若转载，请注明出处：https://www.net2asp.com/63b4fb506f.html