0212. Word Search I I

# 212. Word Search II#

## 题目 #

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example:

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"]

Note:

1. All inputs are consist of lowercase letters a-z.
2. The values of words are distinct.

## 解题思路 #

• 这一题是第 79 题的加强版，在第 79 题的基础上增加了一个 word 数组，要求找出所有出现在地图中的单词。思路还是可以按照第 79 题 DFS 搜索，不过时间复杂度特别高！
• 想想更优的解法。

## 代码 #

package leetcode

func findWords(board [][]byte, words []string) []string {
res := []string{}
for _, v := range words {
if exist(board, v) {
res = append(res, v)
}
}
return res
}

// these is 79 solution
var dir = [][]int{
{-1, 0},
{0, 1},
{1, 0},
{0, -1},
}

func exist(board [][]byte, word string) bool {
visited := make([][]bool, len(board))
for i := 0; i < len(visited); i++ {
visited[i] = make([]bool, len(board[0]))
}
for i, v := range board {
for j := range v {
if searchWord(board, visited, word, 0, i, j) {
return true
}
}
}
return false
}

func isInBoard(board [][]byte, x, y int) bool {
return x >= 0 && x < len(board) && y >= 0 && y < len(board[0])
}

func searchWord(board [][]byte, visited [][]bool, word string, index, x, y int) bool {
if index == len(word)-1 {
return board[x][y] == word[index]
}
if board[x][y] == word[index] {
visited[x][y] = true
for i := 0; i < 4; i++ {
nx := x + dir[i][0]
ny := y + dir[i][1]
if isInBoard(board, nx, ny) && !visited[nx][ny] && searchWord(board, visited, word, index+1, nx, ny) {
return true
}
}
visited[x][y] = false
}
return false
}

Apr 8, 2023