1. 首页

LeetCode 139. 单词拆分

题目描述

给定一个非空字符串 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

难度:Middle

前置知识

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路

这道题是给定一个字典和一个句子,判断该句子是否可以由字典里面的单词组出来,一个单词可以用多次。

暴力的方法是无解的,复杂度极其高。 我们考虑其是否可以拆分为小问题来解决。
对于问题(s, wordDict) 我们是否可以用(s’, wordDict) 来解决。 其中 s’ 是 s 的子序列,
当 s’变成寻常(长度为 0)的时候问题就解决了。 我们状态转移方程变成了这道题的难点。

我们可以建立一个数组 dp, dp[i]代表 字符串 s.substring(0, i) 能否由字典里面的单词组成,
值得注意的是,这里我们无法建立 dp[i] 和 dp[i – 1] 的关系,
我们可以建立的是 dp[i – word.length] 和 dp[i] 的关系。

我们用图来感受一下:

139.word-break-1

没有明白也没有关系,我们分步骤解读一下:

(以下的图左边都代表 s,右边都是 dict,灰色代表没有处理的字符,绿色代表匹配成功,红色代表匹配失败)

139.word-break-2

139.word-break-3

139.word-break-4

139.word-break-5

上面分步解释了算法的基本过程,下面我们感性认识下这道题,我把它比喻为
你正在往一个老式手电筒🔦中装电池

139.word-break-6

代码

/**
 * @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍:是以前端进阶资源教程分享为主的专业网站,包括:前端、大厂面试题、typescript教程、程序人生、React.js
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function (s, wordDict) {
  const dp = Array(s.length + 1);
  dp[0] = true;
  for (let i = 0; i < s.length + 1; i++) {
    for (let word of wordDict) {
      if (word.length <= i && dp[i - word.length]) {
        if (s.substring(i - word.length, i) === word) {
          dp[i] = true;
        }
      }
    }
  }

  return dp[s.length] || false;
};

复杂度分析

更多题解可以访问我的 JS中文网 – 码农周刊 仓库:https://github.com/meibin08/free-programming-books, 一起学习更多前端前沿知识。

看完两件小事

如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:

  1. 关注我们的 GitHub 博客,让我们成为长期关系
  2. 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
  3. 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程

JS中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。欢迎热爱技术的你一起加入交流与学习,JS中文网的使命是帮助开发者用代码改变世界

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com

标题:LeetCode 139. 单词拆分

链接:https://www.javascriptc.com/4503.html

« LeetCode 140. 单词拆分 II
Js中文网周刊第105期»
Flutter 中文教程资源

相关推荐

QR code