[leetcode] wordsearch

problem: https://oj.leetcode.com/problems/word-search/
代码：https://play.golang.org/p/d5wP691Pbg

package main

import (
    "fmt"
)

func main() {
    arr := [][]byte{
        {'A','B','C','E'},{'S','F','S'},{'A','D','E',}
    //word := []byte("ABCESC")
    word := []byte("SFCE")
    arrI,arrJ,ok := FindFirstCharPositions(arr,word[0])
    if ok {
        fmt.Printf("%d,%dn",arrI,arrJ)
    }
    fmt.Println(DFSTraverse(arr,word,arrJ))
}

func DFSTraverse(arr [][]byte,word []byte,arrI []int,arrJ []int) (ret bool) {
    //初始化visited函数
    lenArr := len(arr)
    visited := make([][]bool,lenArr)
    for i := 0; i < lenArr; i++ {
        visited[i] = make([]bool,len(arr[i]))
    }
    lenArrI := len(arrI)
    //lenArrJ := len(arrJ)
    for i := 0; i < lenArrI; i++ {
        //fmt.Println(i)
        ret = DFS(arr,visited,arrI[i],arrJ[i])
        if ret == true {
            return true
        }
    }
    return
}

//dfs traverse,when found return true
func DFS(arr [][]byte,index int,visited [][]bool,i int,j int) (ret bool) {
    if i < 0 || j < 0 || i >= len(visited) || j >= len(visited[i]) || visited[i][j] {
        return false
    }
    if index == len(word) {
        return true
    }
    if arr[i][j] != word[index] {
        return false
    }

    fmt.Printf("%c:%d,%d ",word[index],i,j)
    visited[i][j] = true //标识为已访问
    index++
    //fmt.Println("yes")
    ret = DFS(arr,index,i-1,j) ||
        DFS(arr,j+1) ||
        DFS(arr,i+1,j-1)
    visited[i][j] = false
    return ret
}

func FindFirstCharPositions(arr [][]byte,c byte) (arrI []int,arrJ []int,ok bool) {
    lenArrRow := len(arr)
    if lenArrRow == 0 {
        return
    }
    lenArrCol := len(arr[0])

    for i := 0; i < lenArrRow; i++ {
        for j := 0; j < lenArrCol; j++ {
            if arr[i][j] == c {
                arrI = append(arrI,i)
                arrJ = append(arrJ,j)
                ok = true
            }
        }
    }
    return
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!