This is the 14th day of my participation in the August More Text Challenge
This series is nothing fancy, just pure Leetcode problem breakdown analysis, not to use a sexy line or a niche solution, but with clear code and simple enough thinking to help you clarify the problem. Let you in the interview no longer afraid of algorithm written test.
159. Word break
The label
- medium
- DFS + back
- BFS + back
The title
Leetcode portal
Given a non-empty string s and a list wordDict containing non-empty words, determine whether S can be split by Spaces into one or more words that appear in the dictionary.
Description:
- You can reuse the words in the dictionary when splitting.
- You can assume that there are no duplicate words in the dictionary.
Example 1
Enter: s ="leetcode", wordDict = ["leet"."code"] output:trueExplanation: Returntruebecause"leetcode"It can be split up"leet code".Copy the code
Example 2
Enter: s ="applepenapple", wordDict = ["apple"."pen"] output:trueExplanation: Returntruebecause"applepenapple"It can be split up"apple pen apple"Note that you can reuse words in the dictionary.Copy the code
Example 3
Enter: s ="catsandog", wordDict = ["cats"."dog"."sand"."and"."cat"] output:false
Copy the code
The basic idea
This type of string must be solved by dynamic programming in the first place. But we’re going to look at it in two other ways today.
For example, if the big question is whether the whole string can be sliced, then we can set dp[I] to be
s[0..i]
Before the stringi
To see if it can be split- And then dp[S.length-1] is actually our solution
Of course, we’re going to use two different ideas today.
1. DFS + backtracking
We’ve summarized the template for the DFS + backtracking problem so we can look at it first and then think about our current problem
- We can DFS through all characters
- Set a start pointer and we just have to decide
-
s[0] ~ s[start]
Is a word, if thisIs not a word
.Direct pruning, to backtrack
-
- The remaining substrings recursively determine whether they can be separated into words
-
DFS writing implementation
var wordBreak = function(s, wordDict) {
let res = false, len = s.length
// Use an array to record the case that has been calculated in the history
let cache = new Array(len)
const dfs = (start) = > {
// Recursive exit, indicating that to the end, can be separated, directly true
if (start === len) {
return true
}
// Use the cache directly
if (cache[start]) {
return cache[start]
}
for (let i = start + 1; i <= len; i++) {
const prefix = s.slice(start, i)
Return true if the prefix is a word and the remaining substring can be split
if (wordDict.includes(prefix) && dfs(i)) {
cache[start] = true;
return true; }}// Otherwise the current recursive result is false
cache[start] = false;
return false;
}
// DFS starts with the first element subscript 0
res = dfs(0)
return res
};
let s = "applepenapple", wordDict = ["apple"."pen"]
console.log(wordBreak(s, wordDict))
Copy the code
This method occasionally times out and can be optimized for things like set for dictionaries. Let’s take a look at better BFS
2. BFS + backtracking
- BFS core is kind of a seed in the queue, such as put 0 at the beginning, as the earliest subscript, together with other each element separately, look to whether can match with the words, if you can match, that it is a seed, into the queue, continue to review these seeds, until the queue is empty, we look at the following code.
BFS writing implementation
var wordBreak = function(s, wordDict) {
let len = s.length
let cache = new Array(len)
// This time we use set has instead of include
const wordSet = new Set(wordDict);
// BFS uses queue
const queue = [0];
while (queue.length) {
const start = queue.shift();
// Access skipped
if (cache[start]) continue;
cache[start] = true;
for (let i = start + 1; i <= len; i++) {
const prefix = s.slice(start, i);
if (wordSet.has(prefix)) {
// The prefix is the word, and the I does not exceed the end, continue the division, I as the next seed
if (i < len) {
queue.push(i)
} else {
// At the end, there is nothing left, and the front can be divided up to return true
return true}}}}return false
};
let s = "applepenapple", wordDict = ["apple"."pen"]
console.log(wordBreak(s, wordDict))
Copy the code
In addition, we recommend this series of articles, very simple, on the front of the advanced students are very effective, wall crack recommended!! Core concepts and algorithm disassembly series
If you want to brush the questions with me, you can add me on wechat. Click here to make a friend Or search my wechat account, infinity_9368. You can chat with me and add my secret code “Tianwang Gaidihu”. Verify the message please send me Presious tower shock the rever Monster, I see it through, after adding I will do my best to help you, but pay attention to the way of asking questions, it is suggested to read this article: the wisdom of asking questions
reference
- Leetcode-cn.com/problems/wo…