? ? ? ? leetcode原題鏈接：單詞拆分

題目描述

? ? ? ?給你一個字符串?s?和一個字符串列表?wordDict?作為字典。請你判斷是否可以利用字典中出現的單詞拼接出?s?。注意：不要求字典中出現的單詞全部都使用，并且字典中的單詞可以重復使用。

示例 1：

輸入: s = "leetcode", wordDict = ["leet", "code"]
輸出: true
解釋: 返回 true 因為 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2：

輸入: s = "applepenapple", wordDict = ["apple", "pen"]
輸出: true
解釋: 返回 true 因為"applepenapple"可以由"apple" "pen" "apple" 拼接成。
注意，你可以重復使用字典中的單詞。

示例 3：

輸入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
輸出: false

提示：

• 1 <= s.length <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20
• s?和?wordDict[i]?僅有小寫英文字母組成
• wordDict?中的所有字符串?互不相同

解題方法：動態規劃。

1. 問題定義：dp[k]表示s[0,1,...,k-1],即以第k個字符結尾是否滿足要求

2. 初始化：dp[0]=true,什么都不選，空也是一個集合的子集

3.狀態轉移方程: dp[i] = dp[j] && str[j, i-n]==true

4. 結果返回: dp[n]

C++代碼

#include <iostream>
#include <string>
#include <vector>
#include <set>
/*
* dp[i]表示以s[0,1,...,i-1]是否滿足要求
*     dp[i]= dp[i] || (dp[i-1] && s[i,...,n-1]在wordDict中
*/class Solution {
public:bool wordBreak(std::string s, std::vector<std::string>& wordDict) {int n = s.size();// 1. 問題定義：dp[k]表示s[0,1,...,k-1],即以第k個字符結尾是否滿足要求std::vector<bool> dp(n+1, false); //dp[k]表示s[0,1,...,k-1],即以第k個字符結尾是否滿足要求// 2. 初始化：dp[0]=true,什么都不選，空也是一個集合的子集dp[0] = true; //什么都不選，空也是一個集合的子集// 利用set保存詞典，不用vector初始化std::set<std::string> word_set(wordDict.begin(), wordDict.end());// 3.狀態轉移方程: dp[i] = dp[j] && str[j, i-n]==truefor (int i = 1; i <= n; i++) { //從第1個字符，遍歷到第n個字符// 用s[j]分割第i個字符結尾的字符串for (int j = 0; j < i; j++) { //std::string right_str = s.substr(j, i - j);if (dp[j] && word_set.count(right_str) > 0) { //只要找到一個分割點符合條件，說明字符串滿足要求dp[i] = true;break;}}}// 4. 結果返回: dp[n]return dp[n];//返回以第n個字符結尾的字符串是否滿足要求}
};