| 19 | } |
| 20 | |
| 21 | func explore(board [][]byte, word string, step, r, c int) bool { |
| 22 | // if the step is equal to the length of word, then word exists |
| 23 | if step == len(word) { |
| 24 | return true |
| 25 | } |
| 26 | |
| 27 | // if r or c are out of bounds |
| 28 | if r < 0 || c < 0 || r >= len(board) || c >= len(board[0]) { |
| 29 | return false |
| 30 | } |
| 31 | |
| 32 | // if the character at the step is not the next character in word |
| 33 | if word[step] != board[r][c] { |
| 34 | return false |
| 35 | } |
| 36 | |
| 37 | // if the character has been seen before |
| 38 | if strings.HasPrefix(string(board[r][c]), "_") { |
| 39 | return false |
| 40 | } |
| 41 | |
| 42 | // choose to mark the character as seen |
| 43 | original := board[r][c] |
| 44 | board[r][c] = '_' + original |
| 45 | |
| 46 | // explore each direction in search for word |
| 47 | // short circuit recursion when we've found word |
| 48 | exists := explore(board, word, step+1, r-1, c) || |
| 49 | explore(board, word, step+1, r+1, c) || |
| 50 | explore(board, word, step+1, r, c-1) || |
| 51 | explore(board, word, step+1, r, c+1) |
| 52 | |
| 53 | // un-choose the character |
| 54 | board[r][c] = original |
| 55 | |
| 56 | return exists |
| 57 | } |