LeetCode题解139.word-break

题目地址

https://leetcode.com/problems/word-break/description/

题目描述

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.
Example 1:

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".
Example 2:

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
             Note that you are allowed to reuse a dictionary word.
Example 3:

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

思路

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

暴力的方法是无解的,复杂度极其高。 我们考虑其是否可以拆分为小问题来解决。
对于问题(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] 的关系。

我们用图来感受一下:

LeetCode题解139.word-break

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

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

LeetCode题解139.word-break

LeetCode题解139.word-break

LeetCode题解139.word-break

LeetCode题解139.word-break

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

LeetCode题解139.word-break

代码

/*
 * @lc app=leetcode id=139 lang=javascript
 *
 * [139] Word Break
 *
 * https://leetcode.com/problems/word-break/description/
 *
 * algorithms
 * Medium (34.45%)
 * Total Accepted:    317.8K
 * Total Submissions: 913.9K
 * Testcase Example:  '"leetcode"\n["leet","code"]'
 *
 * Given a non-empty string s and a dictionary wordDict containing a list of
 * non-empty words, determine if s can be segmented into a space-separated
 * sequence of one or more dictionary words.
 *
 * Note:
 *
 *
 * The same word in the dictionary may be reused multiple times in the
 * segmentation.
 * You may assume the dictionary does not contain duplicate words.
 *
 *
 * Example 1:
 *
 *
 * Input: s = "leetcode", wordDict = ["leet", "code"]
 * Output: true
 * Explanation: Return true because "leetcode" can be segmented as "leet
 * code".
 *
 *
 * Example 2:
 *
 *
 * Input: s = "applepenapple", wordDict = ["apple", "pen"]
 * Output: true
 * Explanation: Return true because "applepenapple" can be segmented as "apple
 * pen apple".
 * Note that you are allowed to reuse a dictionary word.
 *
 *
 * Example 3:
 *
 *
 * Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
 * Output: false
 *
 *
 */
/**
 * @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 (dp[i - word.length] && word.length <= i) {
          if (s.substring(i - word.length, i) === word) {
            dp[i] = true;
          }
      }
    }
  }

  return dp[s.length] || false;
};
LeetCode题解堆排序和快速排序

堆排序和快速排序都是时间复杂度$O(nlogn)$ 的算法,其中 n 为数据规模。 那么两者谁更快呢? 为什么?题解:快排最坏情况下是O(n^2),平均和最好是O(nlogn) ,堆排序始终为O(nlogn),还是堆排序快吧

LeetCode题解斜着遍历

遍历是算法的基础。 我们平时看到的 DFS 和 BFS 都是搜索, 而搜索的核心就是遍历,而关键点就是遍历的方式。 从根本上说动态规划也是枚举所有的可能,而枚举就需要用到遍历。 而平时遍历一个二维数组 martrix 的时候, 我们习惯的方式是按行从左到右或者从右到左遍历。 少有情况是按照列遍历, 更少有情况是斜着遍历。那么这次就考考你, 怎么斜着遍历一个二…

LeetCode题解砝码的最小数量

假设有三种重量的砝码,2g、3g、7g,对于任意重量物品,请设计一个函数getResult(weight),接收一个参数weight,返回所需砝码的最小数量。输入示例:const weight = 100;输出示例:getResult(weight) // 15 其中7g的14个,2g的1个题解:```phpfunction getResult($weigh…

LeetCode题解93. 复原IP地址

给定一个只包含数字的字符串,复原它并返回所有可能的 IP 地址格式。有效的 IP 地址正好由四个整数(每个整数位于 0 到 255 之间组成),整数之间用 '.' 分隔。 示例:输入: \"25525511135\"输出: [\"255.255.11.135\", \"255.255.111.35\"]来源:力扣(LeetCode)链接:https://le…

LeetCode题解886. 可能的二分法

给定一组 N 人(编号为 1, 2, ..., N), 我们想把每个人分进任意大小的两组。每个人都可能不喜欢其他人,那么他们不应该属于同一组。形式上,如果 dislikes[i] = [a, b],表示不允许将编号为 a 和 b 的人归入同一组。当可以用这种方法将每个人分进两组时,返回 true;否则返回 false。 示例 1:输入:N = 4, disl…