Keshawn_lu's Blog

Leetcode 139. 单词拆分

动态规划
字数统计: 477阅读时长: 2 min
2020/06/25 Share

题目简介：

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

  • 拆分时可以重复使用字典中的单词。
  • 你可以假设字典中没有重复的单词。

示例 1：

1
2
3
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

示例 2：

1
2
3
4
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
     注意你可以重复使用字典中的单词。

示例 3：

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

思路：

使用动态规划的思想，dp[i]代表0 ~ i - 1的字符串能否被成功拆分。

先将字典中的单词存入哈希表，方便查找。

我们可以将0 ~ i - 1的字符串可以分为0 ~ j - 1和j ~ i - 1，所以dp[i]取决于dp[j]和s.substr(j, i - j)这个字符串是否为单词表中的单词。

所以切割点j的遍历范围每次都为0 ~ i - 1。

tip:

  • 可以在初始化时多分配一个空间，dp[0] = true，代表空串时成功分割单词。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {

        unordered_map<string, int> map;

        for(int i = 0; i < wordDict.size(); i++){

            map[wordDict[i]]++;
        }

        vector<bool> dp(s.size() + 1, false);
        dp[0] = true;   //代表空串为true

        for(int i = 1; i < s.size() + 1; i++){

            for(int j = 0; j < i; j++){ //寻找切割点

                string j_To_i = s.substr(j, i - j);
                if(dp[j] && map[j_To_i]){ //0 ~ j - 1 和 j ~ i - 1都可找到

                    dp[i] = true;
                    break;
                }          
            }
        }

        return dp[s.size()];

    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网