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 stringiTo 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
      1. s[0] ~ s[start]Is a word, if thisIs not a word.Direct pruning, to backtrack
      1. 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…