LeetCode 79,這道走迷宮問題為什麼不能用寬搜呢?

本文始發於個人公眾號:TechFlow,原創不易,求個關注

今天是LeetCode專題第48篇文章,我們一起來看看LeetCode當中的第79題,搜索單詞(Word Search)。

這一題官方給的難度是Medium,通過率是34.5%,點贊3488,反對170。單從這份數據上來看,這題的品質很高,並且難度比之前的題目稍稍大一些。我個人覺得通過率是比官方給的題目難得更有參考意義的指標,10%到20%可以認為是較難的題,30%左右是偏難的題。50%是偏易題,所以如果看到某題標著Hard,但是通過率有50%,要麼說明題目很水,要麼說明數據很水,總有一點很水。

題意

廢話不多說,我們來看題意:

這題的題面挺有意思,給定一個二維的字元型數組,以及一個字元串,要求我們來判斷能否在二維數組當中找到一條路徑,使得這條路徑上的字元連成的字元串和給定的字元串相等?

樣例

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

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

比如第一個字元串ABCCED,我們可以在數組當中找到這樣一條路徑:

題解

不知道大家看到題面和這個樣例有什麼樣的感覺,如果你刷過許多題,經常思考的話,我想應該不難發現,這道題的本質其實和走迷宮問題是一樣的。

我們拿到的這個二維的字元型數組就是一個迷宮, 我們是要在這個迷宮當中找一條「出路」。不過我們的目的不是找到終點,而是找到一條符合題意的路徑。在走迷宮問題當中,迷宮中不是每一個點都可以走的,同樣在當前問題當中,也不是每一個點都符合字元串的要求的。這兩個問題雖然題面看起來大相徑庭,但是核心的本質是一樣的。

我們來回憶一下,走迷宮問題應該怎麼解決?

這個答案應該已經非常確定了,當然是搜索演算法。我們需要搜索解可能存在的空間去尋找存在的解,也就是說我們面臨的是一個解是否存在的問題,要麼找到解,要麼遍歷完所有的可能性發現解不存在。確定了是搜索演算法之後,剩下的就簡單了,我們只有兩個選項,深度優先或者是廣度優先。

理論上來說,一般判斷解的存在性問題,我們使用廣度優先搜索更多,因為一般來說它可以更快地找到解。但是本題當中有一個小問題是,廣度優先搜索需要在隊列當中存儲中間狀態,需要記錄地圖上行走過的資訊,每有一個狀態就需要存儲一份地圖資訊,這會帶來比較大的記憶體開銷,同樣存儲的過程也會帶來計算開銷,在這道題當中,這是不可以接受的。拷貝狀態帶來的空間消耗還是小事,關鍵是拷貝帶來的時間開銷,就足夠讓這題超時了。所以我們別無選擇,只能深度優先。

明確了演算法之後,只剩下了最後一個問題,在這個走迷宮問題當中,我們怎麼找到迷宮的入口呢?因為題目當中並沒有規定我們起始點的位置,這也不難解決,我們遍歷二維的字元數組,和字元串開頭相匹配的位置都可以作為迷宮的入口。

最後,我們來看程式碼,並沒有什麼技術含量,只是簡單的回溯法而已。

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

總結

如果能夠想通回溯法,並且對於回溯法的實現足夠熟悉,那麼這題的難度是不大的。實際上至今為止,我們一路刷來,已經做了好幾道回溯法的問題了,我想對你們來說,回溯法的問題應該已經小菜一碟了。

相比於回溯法來說,我覺得更重要的是我們能夠通過分析想清楚,為什麼廣度優先搜索不行,底層核心的本質原因是什麼。這個思考的過程往往比最後的結論來得重要。

如果喜歡本文,可以的話,請點個關注,給我一點鼓勵,也方便獲取更多文章。

本文使用 mdnice 排版