Nuggets team number online, help you Offer rimmon! Click to see details

Word search (Question number 79)

The title

Given an M x N 2d character grid board and a string word word. Return true if Word exists in the grid; Otherwise, return false.

Words must be formed in alphabetical order by letters in adjacent cells, where “adjacent” cells are those that are contiguous horizontally or vertically. Letters in the same cell are not allowed to be reused.

Example 1:

Input: board = [[" A ", "B", "C", "E"], [" S ", "F", "C", "S"], [" A ", "D", "E", "E"]], the word = "ABCCED" output: trueCopy the code

Example 2:

Input: board = [[" A ", "B", "C", "E"], [" S ", "F", "C", "S"], [" A ", "D", "E", "E"]], the word = "SEE" output: trueCopy the code

Example 3:

Input: board = [[" A ", "B", "C", "E"], [" S ", "F", "C", "S"], [" A ", "D", "E", "E"]], the word = "ABCB" output: falseCopy the code

Tip:

  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • board 和wordConsists of uppercase and lowercase English letters only

link

Leetcode-cn.com/problems/wo…

explain

This themselves are quick to come, but there is a huge long test cases is not, mystery, logic clearly without any problems, no problems with the small test cases, a large amount of data is washed-up, looked at the operation, I differ from the correct answer is it deposit through the path of the use of a two-dimensional array, and I am using a one-dimensional array, Use indexOf to determine whether the current position is inside, it directly uses I and J to locate. As it turns out, that’s where it went wrong

Your own answer (GG)

var exist = function(board, word) {
  var wordArr = word.split('')
  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[i].length; j++) {
      if (board[i][j] === wordArr[0]) {
        if (findMore(1, i, j, [`${i}${j}`])) {
          return true
        }
      }        
    }      
  }    
  function findMore(k, i, j, forbidArr) {
    if (k === wordArr.length) return true
    i += 1
    if (forbidArr.indexOf(`${i}${j}`) < 0 && board[i] && board[i][j] && board[i][j] === wordArr[k]) {
      forbidArr.push(`${i}${j}`)
      if (board[i][j] === wordArr[k] && findMore(k + 1, i, j, forbidArr)) {
        return true
      } else {
        forbidArr.pop()
      }
    }
    i -= 2
    if (forbidArr.indexOf(`${i}${j}`) < 0 && board[i] && board[i][j] && board[i][j] === wordArr[k]) {
      forbidArr.push(`${i}${j}`)
      if (board[i][j] === wordArr[k] && findMore(k + 1, i, j, forbidArr)) {
        return true
      } else {
        forbidArr.pop()
      }
    }
    i += 1
    j += 1
    if (forbidArr.indexOf(`${i}${j}`) < 0 && board[i] && board[i][j] && board[i][j] === wordArr[k]) {
      forbidArr.push(`${i}${j}`)
      if (board[i][j] === wordArr[k] && findMore(k + 1, i, j, forbidArr)) {
        return true
      } else {
        forbidArr.pop()
      }
    }
    j -= 2
    if (forbidArr.indexOf(`${i}${j}`) < 0 && board[i] && board[i][j] && board[i][j] === wordArr[k]) {
      forbidArr.push(`${i}${j}`)
      if (board[i][j] === wordArr[k] && findMore(k + 1, i, j, forbidArr)) {
        return true
      } else {
        forbidArr.pop()
      }
    }
    return false
  }
  return false
};
Copy the code

To be honest, there’s nothing wrong with this approach except that it’s a little ugly. There are some things that need to be streamlined, but it doesn’t stop running. Compelled to look at the answer, the result is the above explanation

Your own answers (backtracking)

This is the second time to do this question, just the last question used backtracking, here also use backtracking to solve the problem 👇 :

var exist = function(board, word) { var len = board.length wid = board[0].length arr = Array.from({length: len}, () => (new Array(wid).fill(false))) function getBack(activeLocation, lastWord) { if (! lastWord) return true const [i, j] = activeLocation for (const [x, y] of [[-1, 0], [1, 0], [0, -1], [0, 1]]) { if (arr[i + x] && ! arr[i + x][j + y] && board[i + x][j + y] === lastWord[0]) { arr[i + x][j + y] = true if (getBack([i + x, j + y], lastWord.substr(1))) { return true } else { arr[i + x][j + y] = false } } } return false } for (let i = 0; i < len; i++) { for (let j = 0; j < wid; j++) { if (board[i][j] === word[0]) { arr[i][j] = true if (getBack([i, j], word.substr(1))) { return true } else { arr[i][j] = false } } } } return false };Copy the code

It should have been a little more concise and put the existence condition first, which would have made the code look simpler, like the findChart at 👇.

A better way (recursion)

var exist = function(board, word) { var forbid = [] for (let i = 0; i < board.length; i++) { forbid[i] = new Array(board[i].length) } for (let i = 0; i < board.length; i++) { for (let j = 0; j < board[i].length; j++) { if (board[i][j] === word[0]) { if (findChart(0, i, j)) { return true } } } } function findChart(k, i, j) { if (k === word.length) return true; if (! board[i] || ! board[i][j]) return false if (forbid[i][j] || board[i][j] ! == word[k]) return false forbid[i][j] = true var findRes = findChart(k + 1, i + 1, j) || findChart(k + 1, i - 1, j) || findChart(k + 1, i, j + 1) || findChart(k + 1, i, j - 1) if (findRes) return true forbid[i][j] = false return false } return false };Copy the code

This method is not the answer, I refer to some of the solutions and operation after a wave of conclusions, is my style But note that forbid here is a two dimensional array, it is good to judge whether there is a need to use the index values only, need not indexOf to search, the difference is actually few, what the result is no problem, outrageous

Here with

Why

To further verify that indexOf was the problem, I wrote something specifically to test execution

The number of cycles is the same, 2,500. IndexOf uses Math.random to get random numbers, while change loops through I and j to get different values. To offset the effect of Math.random, a line of useless code is added to change. My method of writing because of the number of recursion, in such a time-consuming GG is a little normal

var arr = []
for (let i = 0; i < 100; i++) {
  arr[i] = new Array(100)
  for (let j = 0; j < 100; j++) {
    arr[i][j] = `${i}${j}`
  }
}
var newArr = []
for (let i = 0; i < 10000; i++) {
  newArr.push(i)
}
console.time('indexOf')
for (let i = 0; i < 2500; i++) {
  var num = parseInt(Math.random() * 10000)
  var boolean = newArr.indexOf(num)
  newArr[999] = 'fun'
}
console.timeEnd('indexOf')
console.time('change')
for (let i = 0; i < 50; i++) {
  for (let j = 0; j < 50; j++) {
    var num = parseInt(Math.random() * 10000)
    var num = arr[i][j]
    arr[i][j] = 'fun'
  }
}
console.timeEnd('change')
Copy the code

IndexOf: 13.716 ms change: 0.698 ms




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)

Those who are interested can also check out my personal homepage 👇

Here is RZ