Skip to content

Latest commit

 

History

History
147 lines (116 loc) · 4.06 KB

139.word-break.md

File metadata and controls

147 lines (116 loc) · 4.06 KB
Raw

题目地址

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] 的关系。

我们用图来感受一下：

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

代码

/*
 * @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;
};