未分類

Word Search

Array, Backtracking, Go, LeetCode

Word Search

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example:

Given board =

1
2
3
4
5
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

word = “ABCCED”, -> returns true,

word = “SEE”, -> returns true,

word = “ABCB”, -> returns false.

提示 解題應用
Array Array/Slice
Backtracking Recursive

Default:

1
2
3
func exist(board [][]byte, word string) bool {
}

解答思路:

這題最初是直接遍歷整個二元陣列，每遍歷一個字母時就將該字母放入遞回之中找出所有可能(從該字母的上下左右做延伸)，但是接下來就碰上了問題，因為每個位置字母只能夠組合一次，在做上下左右延伸的話很有可能會把同一個位置的字母重覆組合，因此就需要想個辦法來避免這類情況，一開始是打算限制延伸的方向，好比只能向右或向下這類固定的方向延伸，但是題目很清楚的表示只要是鄰近的格子都能延伸，可能某個單字在表上的結果是個S型，所以限制方向這個辦法就沒辦法使用，最後看到比較好的做法是將組合過的字母暫存起來，並再向下遞回延伸之前將該位置的字母替換成特殊字元，待遞回延伸結束後才將該位置的值改回原字母，如此一來如果重覆組合該位置也會因為組合的結果包含特殊字元而與目標值不同回傳false，最後如果發現該單字能由此二元陣列的元素延伸所組成便回傳true，否則就回傳false。

程式碼解說:

如思路所述，因為是先遍歷每個字母當作起頭才做遞回延伸，所以一開始便以兩個迴圈遍歷整個二元陣列，並將每個遍歷字母的位置放入遞回之中，其中第一個參數是已組出的字串，第二、三個參數則用以表示目前遍歷的位置在二元陣列上的第幾橫排第幾直列，第四個與第五個參數則是題目所給予的目標單字與二元陣列，如果該字母起頭做遞回延伸能組出目標單字便直接回傳true，否則就繼續以下一個字母起頭來尋找，待整個二元陣列都遍歷結束如果都還是沒找到符合條件的結果才回傳false

1
2
3
4
5
6
7
8
9
10
func exist(board [][]byte, word string) bool {
	for i := 0; i < len(board); i++ {
		for j := 0; j < len(board[0]); j++ {
			if combine("", i, j, word, board) {
				return true
			}
		}
	}
	return false
}

接下來就是處理遞回延伸的細節，如果上下左右延伸到的位置不在二元陣列的範圍之內便回傳false，取出延伸所在位置的字母做暫存並將該字母與現有字串做組合，組合完畢後便與目標單字做比較，如果完全相同便回傳true，如果與目標單字的前綴不同則直接回傳false，最後就是現有字串與目標單字的前綴暫時相同的情況下要繼續做延伸直到發現完全相的結果，而再次延伸之前先將目前位置的字母替換成特殊字元，接著才往該位置的上下左右做遞回延伸，待遞回延伸結束得到後續結果之後，才將該位置的值改回原字母並向上回傳後續做遞回延伸的結果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func combine(cur string, row int, col int, word string, board [][]byte) bool {
	if row < 0 || col < 0 || row == len(board) || col == len(board[0]) {
		return false
	}
	char := board[row][col]
	cur = cur + string(char)
	if cur == word {
		return true
	} else if cur != word[:len(cur)] {
		return false
	}
	board[row][col] = '#'
	result := combine(cur, row-1, col, word, board) || combine(cur, row, col-1, word, board) || combine(cur, row+1, col, word, board) || combine(cur, row, col+1, word, board)
	board[row][col] = char
	return result
}

完整程式碼:

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
func exist(board [][]byte, word string) bool {
	for i := 0; i < len(board); i++ {
		for j := 0; j < len(board[0]); j++ {
			if combine("", i, j, word, board) {
				return true
			}
		}
	}
	return false
}
func combine(cur string, row int, col int, word string, board [][]byte) bool {
	if row < 0 || col < 0 || row == len(board) || col == len(board[0]) {
		return false
	}
	char := board[row][col]
	cur = cur + string(char)
	if cur == word {
		return true
	} else if cur != word[:len(cur)] {
		return false
	}
	board[row][col] = '#'
	result := combine(cur, row-1, col, word, board) || combine(cur, row, col-1, word, board) || combine(cur, row+1, col, word, board) || combine(cur, row, col+1, word, board)
	board[row][col] = char
	return result
}

總結:

有一二元陣列其中每個元素各代表一個字母，給予一個單字找出該單字是否由能由二元陣列的字母所組成，其中該單字每個元素字母的位置一定要相鄰且不得重覆使用，做法是先直接遍歷整個二元陣列，每遍歷一個字母時就將該字母放入遞回之中找出所有可能(從該字母的上下左右做延伸)，而在延伸的途中將組合過的字母暫存起來，並再向下遞回延伸之前將該位置的字母替換成特殊字元，待遞回延伸結束後才將該位置的值改回原字母，如此一來如果重覆組合該位置也會因為組合的結果包含特殊字元而與目標值不同回傳false，最後如果發現該單字能由此二元陣列的元素延伸所組成便回傳true，否則就回傳false。

分享到