[leetcode]动态规划之wordbreak

短命女 2021-09-28 14:48 444阅读 0赞

### 动态规划之wordbreak ###

*  题目
 *  知识点
 *  思考
 *  代码

# 题目 #

[leetcode入口][leetcode]

# 知识点 #

unordered\_set a(vector.begin(),vector.end()) //哈希set，可以实现快速的查找  
可以使用 a.count(“···”)快速查找

# 思考 #

刚开始被查找字符串难住了，后来看了博客才知道，可以使用哈希set来实现常数时间的查找。

对于每一个dp\[i\]，需要遍历之前的dp\[j\] 0<=j<i,看由j分割的前后两个子串能不能在字典中找到

刚开始想着，判断每个dp\[i\]可能要找到之前某个dp\[j\]为true的情况，判断剩下s\[j…i\]的部分是不是在字典里，但忽略了此时可能整个组合起来可以在字典里找到。因此分割点j，要从0开始一点一点往前移动，整个遍历一遍。

# 代码 #

class Solution { 
    public:
        bool wordBreak(string s, vector<string>& wordDict) { 
            unordered_set<string> dict(wordDict.begin(),wordDict.end()); 
            //哈希set，可以实现常数时间的查找，查找的时候使用.count函数
            
            vector<int> a(s.size()+1);
            a[0]=true;
            
            //对s[1...i]判断能不能由字典中的词切分
            for(int i=1;i<=s.size();i++){ 
                for(int j=0;j<i;j++){ 
                    if(a[j] && dict.count(s.substr(j,i-j))){ 
                        a[i]=true;
                        break;
                    }
                }
            }
            return a[s.size()];
        }
    };

[leetcode]: https://leetcode.com/problems/word-break/

发表评论取消回复

表情：

评论列表（有 0 条评论，444人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode高级算法之动态规划

[152. Maximum Product Subarray][] 这题与最大子序列和不同的地方在于, 乘积的状态转移不能用dp\[i-1\]\num\[i\]来获得, 因为

深藏阁楼爱情的钟/ 2022年12月28日 04:04/ 0 赞/ 195 阅读

相关 leetcode动态规划

1. 爬楼梯假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？动态规划模板题，思考方法，1个台

布满荆棘的人生/ 2022年09月05日 04:07/ 0 赞/ 267 阅读

相关 [leetcode]动态规划之PerfectSquare

动态规划之PerfectSquare 题目思考代码数学方法动态规划题目 [leetcode题目入口][lee

客官°小女子只卖身不卖艺/ 2021年09月29日 02:10/ 0 赞/ 417 阅读

相关 [leetcode]动态规划之Ugly Number

动态规划之Ugly Number 题目思考代码题目 [leetcode入口][leetcode] 思考这是一道结合了数学的dp题

秒速五厘米/ 2021年09月29日 01:52/ 0 赞/ 387 阅读

相关 [leetcode]动态规划之CountingBits

动态规划之CountingBits 题目思考代码题目 [leetcode入口][leetcode] 思考这道题让我思考了dp数组

心已赠人/ 2021年09月29日 01:40/ 0 赞/ 367 阅读

相关 [leetcode]动态规划之Maximal Square

动态规划之Maximal Square 题目思考代码题目 [leetcode入口][leetcode] 思考之前认为dp表格的含

心已赠人/ 2021年09月29日 01:40/ 0 赞/ 457 阅读

相关 [leetcode]动态规划之Largest Plus Sign

动态规划之Largest Plus Sign 题目思考代码暴力法 DP法题目 [leetcode入口][lee

快来打我*/ 2021年09月29日 00:58/ 0 赞/ 296 阅读

相关 [leetcode]动态规划之Maximum Product Subarray

动态规划之Maximum Product Subarray 题目思考类型归类代码题目 [leetcode入口][leetcode]

女爷i/ 2021年09月28日 14:52/ 0 赞/ 391 阅读

相关 [leetcode]动态规划之wordbreak

动态规划之wordbreak 题目知识点思考代码题目 [leetcode入口][leetcode] 知识点 unorder

短命女/ 2021年09月28日 14:48/ 0 赞/ 445 阅读

相关 [leetcode]动态规划之Triangle

动态规划之Triangle 题目思考答案题目 [leetcode入口][leetcode] 思考刚开始想这道题，想着的是建立一维

缺乏、安全感/ 2021年09月28日 14:46/ 0 赞/ 741 阅读