LeetCode之單詞搜索(回溯法求解)

題目

給定一個 m x n 二維字符網格 board 和一個字符串單詞 word 。如果 word 存在於網格中，返回 true ；否則，返回 false 。

單詞必須按照字母順序，通過相鄰的單元格內的字母構成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個單元格內的字母不允許被重複使用。

示例 1：

輸入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
輸出：true
示例 2：

輸入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
輸出：true
示例 3：

輸入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
輸出：false
 

提示：

m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board 和 word 僅由大小寫英文字母組成

來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/word-search
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

思路

因為前不久剛做過一個走迷宮的問題，所以在讀完這題後，就發現它與走迷宮驚奇的相似，只不過在走下一步的時候條件有所改變。但是，它還是花了我2個多接近3個小時才寫出來的！，唉，不說了，還是我太菜了。

言歸正傳（菜不能做為我懶惰的理由）

首先，不管是走迷宮還是這一題，都得有一個起點，對於這一題，如果一個一個去試的話，那樣就太費時了，所以我首先遍曆了整個網格， 找到和要查找的單詞的第一個字母一樣的字母的比特置：

 start_pos_li = []  # 記錄單詞首字母的比特置
        word_set = set()  # 錶格中的所有字母
        m, n = len(board), len(board[0])
        for i in range(m):
            for j in range(n):
                word_set.add(board[i][j])
                if board[i][j] == word[0]:
                    start_pos_li.append((i, j))

找到的字母添加到start_pos_li這個列錶中，方便以後查找直接從這些比特置開始。

同時我也設置了一個集合word_set，保存網格中所有出現的字母，在正式查找之前，可以做一個簡單的判斷來快速得出一些栗子的答案：

        for s in word:
            if s not in word_set: return False  # 只要有一個字母不在錶格中就返回False

如代碼所示，遍曆需要查找的單詞，只要有一個字母不在集合中就直接返回False。

下面就開始正式的查找

 1.首先定義一個移動規則：

 # 移動(四個方向)
    def move(self, x, y, direction):
        if direction == 1:
            return (x - 1, y)
        elif direction == 2:
            return (x + 1, y)
        elif direction == 3:
            return (x, y - 1)
        else:
            return (x, y + 1)

1代錶上移，2代錶下移，3代錶左移，4代錶右移；我這裏是以橫軸作為y軸，縱軸作為x軸，所以 上下移動的時候x軸發現變化，左右移動的時候y軸發生變化。

2.開始試探性的走

a.定義一個“棧”來保存走過的路徑

path = [start]  # 記錄走過的路徑

其實這裏就是一個列錶，但是只使用append()和pop()方法，那麼它的行為就像棧。

b.定義一個列錶保存每一個格子走過的方向

visit_li = [[set() for j in range(n)] for i in range(m)]  # 記錄當前比特置到下一步走過的方向

這裏每一個格子走過的方向我用的是一個集合來存儲的，一個格子最多存儲四個方向，即上下左右；與走迷宮不一樣的是，在走迷宮中就用來兩個值來錶示：0代錶當前格子沒有走過，1代錶當前格子已走；因為這裏的是一個單詞，它要求的是一個連續的序列，當前格子從這個方向過來可能不行，但是從另外一個方向過來就可以。（即從不同的方向取格子，所得到的序列都是不同的）

c.試探+回溯

# 從起始字母開始尋找
        for start in start_pos_li:
            path = [start]  # 記錄走過的路徑
            visit_li = [[set() for j in range(n)] for i in range(m)]  # 記錄當前比特置到下一步走過的方向
            while path:
                # print(path)
                if len(path) == len(word): return True  # 只要走過的路徑和單詞的長度相同就說明走完了
                cur_pos = path[-1]  # 當前比特置(m,n)
                for step in range(4):  # 四個方向分別探尋
                    next_pos = self.move(*cur_pos, step)  # 下一步
                    if 0 <= next_pos[0] < m and 0 <= next_pos[1] < n and step not in visit_li[cur_pos[0]][
                        cur_pos[1]] and next_pos not in set(path):  # 下一步可走且沒有走過
                        if board[next_pos[0]][next_pos[1]] == word[len(path)]:  # 下一步比特置的字母和需要的字母相同
                            path.append(next_pos)  # 就移動到下一步
                            visit_li[cur_pos[0]][cur_pos[1]].add(step)  # 標記該比特置已走過
                            break
                    else:
                        visit_li[cur_pos[0]][cur_pos[1]].add(step)  # 標記這個方向走不通
                else:
                    x, y = path.pop()  # 四個方向都走不了就回退
                    visit_li[x][y] = set()  # 同時清空該比特置已走過的方向

從起點開始，依次試探四個方向是否可走，如果可走更新可走點為當前比特置，然後繼續試探，如果到某一點，四個方向都行不通，則回溯，退回到上一步；繼續上次沒有走完的方向，以下面這個栗子為例：

源碼

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        '''
        類似於走迷宮，設置4個移動方向，同時標記走過的地方
        '''

        start_pos_li = []  # 記錄單詞首字母的比特置
        word_set = set()  # 錶格中的所有字母
        m, n = len(board), len(board[0])
        for i in range(m):
            for j in range(n):
                word_set.add(board[i][j])
                if board[i][j] == word[0]:
                    start_pos_li.append((i, j))

        for s in word:
            if s not in word_set: return False  # 只要有一個字母不在錶格中就返回False

        # 從起始字母開始尋找
        for start in start_pos_li:
            path = [start]  # 記錄走過的路徑
            visit_li = [[set() for j in range(n)] for i in range(m)]  # 記錄當前比特置到下一步走過的方向
            while path:
                # print(path)
                if len(path) == len(word): return True  # 只要走過的路徑和單詞的長度相同就說明走完了
                cur_pos = path[-1]  # 當前比特置(m,n)
                for step in range(4):  # 四個方向分別探尋
                    next_pos = self.move(*cur_pos, step)  # 下一步
                    if 0 <= next_pos[0] < m and 0 <= next_pos[1] < n and step not in visit_li[cur_pos[0]][
                        cur_pos[1]] and next_pos not in set(path):  # 下一步可走且沒有走過
                        if board[next_pos[0]][next_pos[1]] == word[len(path)]:  # 下一步比特置的字母和需要的字母相同
                            path.append(next_pos)  # 就移動到下一步
                            visit_li[cur_pos[0]][cur_pos[1]].add(step)  # 標記該比特置已走過
                            break
                    else:
                        visit_li[cur_pos[0]][cur_pos[1]].add(step)  # 標記這個方向走不通
                else:
                    x, y = path.pop()  # 四個方向都走不了就回退
                    visit_li[x][y] = set()  # 同時清空該比特置已走過的方向
            # print('*' * 100)
        return False

    # 移動(四個方向)
    def move(self, x, y, direction):
        if direction == 1:
            return (x - 1, y)
        elif direction == 2:
            return (x + 1, y)
        elif direction == 3:
            return (x, y - 1)
        else:
            return (x, y + 1)

通過截圖

同步更新於個人博客系統：LeetCode之單詞搜索(回溯法求解)