Voyz's Studio.

LeetCode算法笔记--单词拆分

字数统计: 265阅读时长: 1 min
2021/01/02 Share

LeetCode算法笔记-Day56

139. Word Break

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
example:

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

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.
 
Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

方法一:回溯算法

Analyse:

位运算.png

Answer:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* @param {string} s
* @param {string[]} wordDict
* @return {boolean}
*/
var wordBreak = function (s, wordDict) {
const wordSet = new Set(wordDict);
const len = s.length;
const dp = new Array(len + 1).fill(false);
dp[0] = true;
for (let i = 1; i <= len; i++) {
for (let j = i - 1; j >= 0; j--) {
if (dp[i] == true) break;
if (dp[j] == false) continue;
const word = s.slice(j, i);
if (wordSet.has(word) && dp[j] == true) {
dp[i] = true;
break;
}
}
}
return dp[s.length];
};
CATALOG
  1. 1. LeetCode算法笔记-Day56
    1. 1.1. 139. Word Break
    2. 1.2. 方法一:回溯算法
      1. 1.2.1. Analyse:
      2. 1.2.2. Answer: