2021-10-02: word search. Given an M x n two-dimensional character grid boa

2021-10-02： Word search . Given a m x n Two dimensional character grid board And a string word word . If word Exists in the grid , return true ; otherwise , return false . The words must be in alphabetical order , It's made up of letters in adjacent cells , among “ adjacent ” Cells are those adjacent horizontally or vertically . Letters in the same cell are not allowed to be reused . Power button 79.

Fuda answer 2021-10-02：

Natural intelligence is enough .

recursive . about boardi, Go up, down, left and right .1. Manufacturing site ;2. recursive ;3. Restore the scene .

The code to use golang To write . The code is as follows ：

package main

import "fmt"

func main() {
    board := [][]byte{{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}}
    word := "ABCCED"
    ret := exist(board, word)
    fmt.Println(ret)
}

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

//  It has arrived b[i][j],word[k....]
//  from b[i][j] set out , Can we take care of it word[k....] true false
func f(b [][]byte, i int, j int, w []byte, k int) bool {
    if k == len(w) {
        return true
    }
    // word[k.....]  Have a character 
    //  If (i,j) Transboundary , return false
    if i < 0 || i == len(b) || j < 0 || j == len(b[0]) {
        return false
    }
    if b[i][j] != w[k] {
        return false
    }
    tmp := b[i][j]
    b[i][j] = 0
    ans := f(b, i-1, j, w, k+1) || f(b, i+1, j, w, k+1) || f(b, i, j-1, w, k+1) || f(b, i, j+1, w, k+1)
    b[i][j] = tmp
    return ans
}

The results are as follows ：

picture

---

Zuo Shen java Code