This is the 15th day of my participation in the August More Text Challenge. For details, see:August is more challenging

(Question number 139)

The title

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 occur in the dictionary.

Description:

  • You can reuse words from the dictionary when you break them up.
  • 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 broken up"leet code".Copy the code

Example 2:

Enter: s ="applepenapple", wordDict = ["apple"."pen"] output:trueExplanation: Returntruebecause"applepenapple"It can be broken up"apple pen apple". Note that you can reuse words from the dictionary.Copy the code

Example 3:

Enter: s ="catsandog", wordDict = ["cats"."dog"."sand"."and"."cat"] output:false
Copy the code

link

Leetcode-cn.com/problems/wo…

explain

This one, this is classic DP.

If the current word is in the dictionary, then reset the word. So if the current word is not empty at the end of the loop, then return false. If it is empty at the end of the loop, then return false. That proves that the string can be made up of words from the dictionary.

The code is also simple 👇 :

var wordBreak = function(s, wordDict) {
  const set = new Set(wordDict)
  let word = ' '
  for (const char of s) {
    word += char
    if (set.has(word)) {
      word = ' '}}return! word };Copy the code

One test case left me baffled, and here it is:

"aaaaaaa"
["aaaa"."aaa"]
Copy the code

Why did this test case break down? It’s pretty simple, because it’s supposed to be a string consisting of aaaa and aaa, but according to the logic of the code above, if I see aaa, I’ll truncate it once, so I’ll still have aaaa, if I see aaa, I’ll truncate it again, and then I’ll just have an A, and then GG.

The problem is that when you get to the fourth character, you should be able to keep going, you shouldn’t just cut it off, so you come up with the second solution — recursion.

Use recursion to cover untried possibilities so that you have a wide coverage.

Specifically in the answer to explain, here does not take up space.

After using the recursion and looking at the official answer, in fact, DP can also be solved, and seems to be much simpler.

If both DP [0~ I] and DP [I ~n] meet the conditions of the dictionary, then prove that the current DP [I] is qualified. Then split I, and use the loop to find the combination of 0~j and j~ I little by little. If the conditions are met, prove that DP [I] meets the conditions.

To tell the truth, it is still better to understand, and the overall idea is more in line with the overall idea of DP, first of all recursion, recursion after the use of memory optimization, and finally deduce DP.

Your own answer (recursion)

The idea of recursion is also simple, and all possibilities must be considered in order to avoid missing problems.

So you need to start at all of the locations in the array, and if the current word is in the dictionary, you need to determine if the rest of the word is in the dictionary, and return true if it is, and false if it is not.

var wordBreak = function(s, wordDict) {
  const len = s.length
  const set = new Set(wordDict)
  function DFS(start) {
    if (start === len) return true
    for (let i = start + 1; i <= len; i++) {
      if (set.has(s.slice(start, i)) && DFS(i)) return true
    }
    return false
  }
  return DFS(0)}Copy the code

The answer, of course, is not as simple as that, as the 34th long test case was executed, because there was a lot of double-counting and wasted performance.

Your own answers (recursion + memorization)

To optimize recursion, you first have to figure out where duplicate data occurs. Look at the code for 👆 and you’ll see that I has a lot of duplications. Here’s an example:

"aaaaaaa"
["aaaa"."aaa"]
Copy the code

I must have tried 0 to 6 in the beginning, and when I hit 2, start becomes 3 and I go, so it’s going to be successful here, but what if it doesn’t? It’s going to go into the next for loop, so it’s going to try the same number again, so there should be something here that keeps track of the results of the current attempt, whether it’s a failure or a success, to avoid further double counting.

var wordBreak = function(s, wordDict) {
  const len = s.length
  const set = new Set(wordDict)
  const map = new Map(a)function DFS(start) {
    if (start === len) return true
    if (map.has(start)) return map.get(start)
    for (let i = start + 1; i <= len; i++) {
      if (set.has(s.slice(start, i)) && DFS(i)) {
        map.set(i, true)
        return true
      }
    }
    map.set(start, false)
    return false
  }
  return DFS(0)}Copy the code

Simply use a Map to record, to achieve memory operation, so you can go through all the test cases.

A better approach (dynamic Programming)

The idea of DP is already explained in the explanation, directly look at the code:

var wordBreak = function(s, wordDict) {
  const len = s.length
  const set = new Set(wordDict)
  const dp = new Array(len + 1).fill(false)
  dp[0] = true
  for (let i = 0; i <= len; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && set.has(s.substr(j, i - j))) {
        dp[i] = true
        break}}}return dp[len]
};
Copy the code

The main thing is to break the possibilities down into each element of the DP array, and then break the I into j to do the segmentation, which is relatively easy to understand.




PS: To view past articles and titles, click on the link below:

Here’s 👇 by date

Front Brush path – Directory (Date classification)

After some friends remind, the feeling should also be classified according to the type of questions here is in accordance with the type of 👇

Front brush problem path – Catalogue (Question type classification)