[LeetCode] Word Break 拆分词句

简介:

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

这道拆分词句问题是看给定的词句能分被拆分成字典里面的内容,还是需要用动态规划Dynamic Programming来做,具体讲解可参考网友Code Ganker的博客,代码如下:

class Solution {
public:
    bool wordBreak(string s, unordered_set<string> &dict) {
        int len = s.size();
        vector<bool> res(len + 1, false);
        res[0] = true;
        for (int i = 0; i < len + 1; ++i) {
            for (int j = 0; j < i; ++j) {
                if (res[j] && dict.find(s.substr(j, i-j)) != dict.end()) {
                    res[i] = true;
                    break;
                }
            }
        }
        return res[len];
    }
};

本文转自博客园Grandyang的博客,原文链接:拆分词句[LeetCode] Word Break ,如需转载请自行联系原博主。

相关文章
|
6月前
|
人工智能 BI
力扣561 数组拆分
力扣561 数组拆分
|
6月前
|
Java C++
leetcode-139:单词拆分
leetcode-139:单词拆分
60 0
|
3月前
|
Python
【Leetcode刷题Python】343. 整数拆分
LeetCode 343题 "整数拆分" 的Python解决方案,使用动态规划算法来最大化正整数拆分为多个正整数之和的乘积。
26 0
|
6月前
|
存储 索引
leetcode139单词拆分刷题打卡
leetcode139单词拆分刷题打卡
45 0
|
6月前
leetcode代码记录(整数拆分
leetcode代码记录(整数拆分
47 0
|
6月前
|
算法 测试技术
代码随想录 Day39 动态规划 LeetCode T139 单词拆分 动规总结篇1
代码随想录 Day39 动态规划 LeetCode T139 单词拆分 动规总结篇1
59 0
|
6月前
|
算法
代码随想录Day34 LeetCode T343整数拆分 T96 不同的二叉搜索树
代码随想录Day34 LeetCode T343整数拆分 T96 不同的二叉搜索树
53 0
|
6月前
|
Go
golang力扣leetcode 139.单词拆分
golang力扣leetcode 139.单词拆分
42 0
|
6月前
leetcode-343:整数拆分
leetcode-343:整数拆分
41 0
【LeetCode 热题 HOT 100】139. 单词拆分【中等】
【LeetCode 热题 HOT 100】139. 单词拆分【中等】