婚纱摄影网站设计理念,甘肃兰州天气预报15天,管理网站,专业电商网站leetcode原题链接#xff1a;单词拆分
题目描述 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。注意#xff1a;不要求字典中出现的单词全部都使用#xff0c;并且字典中的单词可以重复使用。
示例 1#xff1a… 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 3001 wordDict.length 10001 wordDict[i].length 20s 和 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::vectorstd::string wordDict) {int n s.size();// 1. 问题定义dp[k]表示s[0,1,...,k-1],即以第k个字符结尾是否满足要求std::vectorbool dp(n1, false); //dp[k]表示s[0,1,...,k-1],即以第k个字符结尾是否满足要求// 2. 初始化dp[0]true,什么都不选空也是一个集合的子集dp[0] true; //什么都不选空也是一个集合的子集// 利用set保存词典不用vector初始化std::setstd::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个字符结尾的字符串是否满足要求}
};
