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

Word Search II (Question 212)

The title

Given an M x N 2d character grid board and a list of words (strings), find all the words that appear in both the 2D grid and the dictionary.

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 used more than once in a word.

Example 1:

Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], Words = [" oath ", "pea", "eat", "rain"] output: [" eat ", "oath"]Copy the code

Example 2:

Input: board = [[" a ", "b"], [" c ", "d"]], words = [" abcb "] output: []Copy the code

Tip:

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 12
  • board[i][j]It’s a lowercase letter
  • 1 <= words.length <= 3 * 104
  • 1 <= words[i].length <= 10
  • words[i]It consists of lowercase letters
  • wordsAll the strings in the

link

Leetcode-cn.com/problems/wo…

explain

Although this question is difficult, but feel difficult in the idea, the specific content is actually not complicated.

The key is the combination of the dictionary tree and recursion. You get the dictionary tree, then you walk through the board, and when you find the right one, you walk right through it.

Traversal may be bad to understand, in fact, the layers to get the dictionary tree node traversal, due to the dictionary may have multiple bifurcate tree, need to continue to traverse in the fork, so right now you need to add existing words when existing words into res, note at this time can’t stop traversal, should continue to traverse, otherwise the rest of the split cannot be traversed to, result in failure,

So basically, the bifurcation of the dictionary tree and the bifurcation of the recursion come together in a way that normal people can hardly imagine.

Your own answer

There is no

A better way (dictionary tree)

var findWords = function(board, words) { var res = [] row = board.length col = board[0].length trie = {} dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] for (const word of words) { var node = trie for (const chart of word) { if (! node[chart]) node[chart] = {} node = node[chart] } node.word = word } function findChart(root, i ,j) { if (root.word) { res.push(root.word) root.word = null } if (i >= row || j >= col || i < 0 || j < 0) return if (! root[board[i][j]]) return var currentChart = board[i][j] board[i][j] = false for (let k = 0; k < 4; k++) { findChart(root[currentChart], i + dx[k], j + dy[k]) } board[i][j] = currentChart return } for (let i = 0; i < row; i++) { for (let j = 0; j < col; j++) { findChart(trie, i, j) } } return res };Copy the code




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