题目地址
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] 的关系。
我们用图来感受一下:
没有明白也没有关系,我们分步骤解读一下:
(以下的图左边都代表s,右边都是dict,灰色代表没有处理的字符,绿色代表匹配成功,红色代表匹配失败)
上面分步解释了算法的基本过程,下面我们感性认识下这道题,我把它比喻为
你正在往一个老式手电筒?中装电池
代码
/* * @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…