79.Word_Search.md

79. Word Search

這題是很經典的 Backtracking 問題，這邊我們先來思考:

1. 這題的開頭並不是固定的，要怎麼找到開頭的位置
   • 這邊我們可以用雙層迴圈來找到開頭的位置，在這個位置開始進行 Backtracking
2. 因為是 Matrix，所以需要定義移動的方向
3. 要怎麼紀錄已經走過的道路

Time Complexity $O(N \cdot 4^L)$, 4 是因為有 4 個方向可以走，L 是 word 的長度，Space Complexity $O(L)$

Recursive

Recursive Solution:

• 這裡要注意 Golang 的特性，之前使用過另一個 Deep copy 的方法但是速度會慢非常多，所以這邊我們直接在原本的 board 上面進行修改

var (
	directions = [][]int{{0, -1}, {0, 1}, {1, 0}, {-1, 0}}
)

func exist(board [][]byte, word string) bool {
	for i := range board {
		for j := range board[i] {
			if board[i][j] == word[0] {
				temp := board[i][j]
				board[i][j] = 0
				if backtracking(board, word[1:], i, j) {
					return true
				}
				board[i][j] = temp
			}
		}
	}
	return false
}

func backtracking(board [][]byte, word string, x, y int) bool {
	if len(word) <= 0 {
		return true
	}
	for _, d := range directions {
		nx, ny := x+d[0], y+d[1]
		if !(nx >= 0 && nx < len(board) && ny >= 0 && ny < len(board[nx])) {
			continue
		}
		if board[nx][ny] != 0 && board[nx][ny] == word[0] {
			temp := board[nx][ny]
			board[nx][ny] = 0
			if backtracking(board, word[1:], nx, ny) {
				return true
			}
			board[nx][ny] = temp
		}
	}
	return false
}

在這個解法上可以去試著 Local Optimization，例如在進入 backtracking 之前可以先檢查是否有可能找到，如果不可能就不用進入 backtracking 這個過程。

Local Optimization:

• 只檢查是否有可能找到，就能擠進 98% 的執行時間

func isExist(board [][]byte, word string) bool {
	hash1, hash2 := map[byte]int{}, map[byte]int{}
	for i := range board {
		for j := range board[i] {
			hash1[board[i][j]]++
		}
	}
	for i := range word {
		hash2[word[i]]++
	}
	for k := range hash2 {
		if _, exist := hash1[k]; !exist {
			return false
		}
		if hash2[k] > hash1[k] {
			return false
		}
	}
	return true
}

---

Iterative

這題也可以不用 Recursive 來解，但是這題處理起來會比較麻煩，目前這樣的寫法並不是最佳解，但是可以通過測試。如果想要讓 Iterative 的寫法更好， 需要更高效的去處理已經走過的路徑，並且不要使用太複雜的資料結構。

Iterative Solution:

• 使用一個 2D Array 來紀錄已經走過的路徑，並且要設定一個新的棋盤來更新走過的路徑

var (
	directions = [][]int{{0, -1}, {0, 1}, {1, 0}, {-1, 0}}
	stack      = []BoardState{}
)

type BoardState struct {
	x, y int
	word string
	path [][]int
}

func exist(board [][]byte, word string) bool {
	if !isExist(board, word) {
		return false
	}
	startPositions := getStart(board, word[0])
	stack = []BoardState{}
	for _, pos := range startPositions {
		x, y := pos[0], pos[1]
		stack = append(stack, BoardState{x, y, word[1:], [][]int{pos}})
		if search(board) {
			return true
		}
	}
	return false
}

func search(board [][]byte) bool {
	for len(stack) > 0 {
		state := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		if len(state.word) <= 0 {
			return true
		}
		temp := copyBoard(board)
		for _, p := range state.path {
			temp[p[0]][p[1]] = 0
		}
		for _, d := range directions {
			x, y := d[0]+state.x, d[1]+state.y
			if !(x >= 0 && x < len(temp) && y >= 0 && y < len(temp[x])) {
				continue
			}
			if temp[x][y] == 0 {
				continue
			}
			if temp[x][y] == state.word[0] {
				new_path := make([][]int, len(state.path))
				copy(new_path, state.path)
				new_path = append(new_path, []int{x, y})
				stack = append(stack, BoardState{x, y, state.word[1:], new_path})
			}
		}
	}
	return false
}

func getStart(board [][]byte, start byte) [][]int {
	res := [][]int{}
	for i := range board {
		for j := range board[i] {
			if board[i][j] == start {
				res = append(res, []int{i, j})
			}
		}
	}
	return res
}

func copyBoard(board [][]byte) [][]byte {
	newBoard := make([][]byte, len(board))
	for i := range board {
		newBoard[i] = make([]byte, len(board[i]))
		copy(newBoard[i], board[i])
	}
	return newBoard
}

func isExist(board [][]byte, word string) bool {
	hash1, hash2 := map[byte]int{}, map[byte]int{}
	for i := range board {
		for j := range board[i] {
			hash1[board[i][j]]++
		}
	}
	for i := range word {
		hash2[word[i]]++
	}
	for k := range hash2 {
		if _, exist := hash1[k]; !exist {
			return false
		}
		if hash2[k] > hash1[k] {
			return false
		}
	}
	return true
}