​LeetCode刷題實戰79:單詞搜索

算法的重要性，我就不多說了吧，想去大廠，就必須要經過基礎知識和業務邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號後續每天帶大家做一道算法題，題目就從LeetCode上面選 ！

今天和大家聊的問題叫做 單詞搜索，我們先來看題面：

https://leetcode-cn.com/problems/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 cells, where "adjacent" cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

題意給定一個二維網格和一個單詞，找出該單詞是否存在於網格中。單詞必須按照字母順序，通過相鄰的單元格內的字母構成，其中「相鄰」單元格是那些水平相鄰或垂直相鄰的單元格。同一個單元格內的字母不允許被重複使用。

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

給定 word = "ABCCED", 返回 true
給定 word = "SEE", 返回 true
給定 word = "ABCB", 返回 false

比如第一個字符串ABCCED，我們可以在數組當中找到這樣一條路徑：解題https://www.cnblogs.com/techflow/p/13180855.html題解如果你刷過許多題，經常思考的話，我想應該不難發現，這道題的本質其實和走迷宮問題是一樣的。我們拿到的這個二維的字符型數組就是一個迷宮， 我們是要在這個迷宮當中找一條「出路」。不過我們的目的不是找到終點，而是找到一條符合題意的路徑。在走迷宮問題當中，迷宮中不是每一個點都可以走的，同樣在當前問題當中，也不是每一個點都符合字符串的要求的。這兩個問題雖然題面看起來大相逕庭，但是核心的本質是一樣的。這個答案應該已經非常確定了，當然是搜索算法。我們需要搜索解可能存在的空間去尋找存在的解，也就是說我們面臨的是一個解是否存在的問題，要麼找到解，要麼遍歷完所有的可能性發現解不存在。確定了是搜索算法之後，剩下的就簡單了，我們只有兩個選項，深度優先或者是廣度優先。理論上來說，一般判斷解的存在性問題，我們使用廣度優先搜索更多，因為一般來說它可以更快地找到解。但是本題當中有一個小問題是，廣度優先搜索需要在隊列當中存儲中間狀態，需要記錄地圖上行走過的信息，每有一個狀態就需要存儲一份地圖信息，這會帶來比較大的內存開銷，同樣存儲的過程也會帶來計算開銷，在這道題當中，這是不可以接受的。拷貝狀態帶來的空間消耗還是小事，關鍵是拷貝帶來的時間開銷，就足夠讓這題超時了。所以我們別無選擇，只能深度優先。明確了算法之後，只剩下了最後一個問題，在這個走迷宮問題當中，我們怎麼找到迷宮的入口呢？因為題目當中並沒有規定我們起始點的位置，這也不難解決，我們遍歷二維的字符數組，和字符串開頭相匹配的位置都可以作為迷宮的入口。最後，我們來看代碼，並沒有什麼技術含量，只是簡單的回溯法而已。

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        fx = [[0, 1], [0, -1], [1, 0], [-1, 0]]
        def dfs(x, y, l):
            if l == len(word):
                return True
            for i in range(4):
                nx = x + fx[i][0]
                ny = y + fx[i][1]
                # 出界或者是走過的時候，跳過
                if nx < 0 or nx == n or ny < 0 or ny == m or visited[nx][ny]:
                    continue
                if board[nx][ny] == word[l]:
                    visited[nx][ny] = 1
                    if dfs(nx, ny, l+1):
                        return True
                    visited[nx][ny] = 0
            return False
                
        n = len(board)
        if n == 0:
            return False
        m = len(board[0])
        if m == 0:
            return False
        
        visited = [[0 for i in range(m)] for j in range(n)]
        
        for i in range(n):
            for j in range(m):
                # 找到合法的起點
                if board[i][j] == word[0]:
                    visited = [[0 for _ in range(m)] for _ in range(n)]
                    visited[i][j] = 1
                    if dfs(i, j, 1):
                        return True
                    
        return False

總結如果能夠想通回溯法，並且對於回溯法的實現足夠熟悉，那麼這題的難度是不大的。實際上至今為止，我們一路刷來，已經做了好幾道回溯法的問題了，我想對你們來說，回溯法的問題應該已經小菜一碟了。相比於回溯法來說，我覺得更重要的是我們能夠通過分析想清楚，為什麼廣度優先搜索不行，底層核心的本質原因是什麼。這個思考的過程往往比最後的結論來得重要。好了，今天的文章就到這裡，如果覺得有所收穫，請順手點個在看或者轉發吧，你們的支持是我最大的動力。