-
Notifications
You must be signed in to change notification settings - Fork 17
/
word-search.go
63 lines (58 loc) · 1.6 KB
/
word-search.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
package main
func exist(board [][]byte, word string) bool {
rows, cols := len(board), len(board[0])
createVisited := func(rows, cols int) [][]bool {
result := [][]bool{}
for row := range make([]bool, rows) {
result = append(result, []bool{})
for _ = range make([]bool, cols) {
result[row] = append(result[row], false)
}
}
return result
}
neighbours := func(row, col int, visited *[][]bool) [][]int {
tmp := [][]int{}
tmp = append(tmp, []int{row - 1, col})
tmp = append(tmp, []int{row + 1, col})
tmp = append(tmp, []int{row, col - 1})
tmp = append(tmp, []int{row, col + 1})
result := [][]int{}
for _, neighbour := range tmp {
neighRow, neighCol := neighbour[0], neighbour[1]
if neighRow >= 0 && neighRow < rows && neighCol >= 0 && neighCol < cols {
if !(*visited)[neighRow][neighCol] {
result = append(result, []int{neighRow, neighCol})
}
}
}
return result
}
var backtrack func(row, col int, wordPos int, visited *[][]bool) bool
backtrack = func(row, col int, wordPos int, visited *[][]bool) bool {
if word[wordPos] != board[row][col] {
return false
}
if wordPos == len(word)-1 {
return true
}
for _, neighbour := range neighbours(row, col, visited) {
neighRow, neighCol := neighbour[0], neighbour[1]
(*visited)[row][col] = true
if backtrack(neighRow, neighCol, wordPos+1, visited) {
return true
}
(*visited)[row][col] = false
}
return false
}
visited := createVisited(rows, cols)
for row := range board {
for col := range board[0] {
if backtrack(row, col, 0, &visited) {
return true
}
}
}
return false
}