單詞搜索Leetcode解決方案  


難度級別 中烘焙
經常問 亞馬遜 蘋果 彭博社 ByteDance 思科 易趣 Expedia的 Facebook 意會 Microsoft微軟 神諭 Pinterest 的ServiceNow Snapchat
算法 回溯 編碼 訪問 面試準備 力碼 力碼解決方案 矩陣

問題陳述  

給定一個mxn板和一個單詞,請查找單詞是否存在於網格中。

該單詞可以由順序相鄰的單元格的字母構成,其中“相鄰”的單元格在水平或垂直方向上相鄰。 同一字母單元不得重複使用。

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

word = "ABCCED"
true

說明:

單詞搜索Leetcode解決方案

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

word = "ABCB"
false

方法(回溯)  

這是一個二維網格遍歷問題,我們必須探索網格以檢查是否可以使用網格的相鄰單元格來形成給定的單詞。 但是,除了在整個網格空間上執行DFS之外,我們還可以更好地使用回溯方法。 在回溯方法中,我們只會走那條路找到符合我們目標的解決方案。 如果在某個時候我們知道當前路徑不會導致解決方案,那麼我們將回溯並尋求下一個選擇。

我們將在每一步中將當前單元格標記為已遍歷,從而繞過網格。 在每個步驟的最後,我們也將其取消標記,以便我們可以有一個乾淨的狀態來嘗試另一個方向。

單詞搜索Leetcode解決方案

算法  

我們將創建一個回溯功能,該功能將從一個特定的單元格開始,並以DFS方式遍歷網格的相鄰單元格。 因為給定的單詞可以從網格中的任何位置開始,所以我們將遍歷網格的所有單元,對於每個單元,我們將從當前單元開始調用回溯功能。
由於此回溯功能是 遞歸 函數,以下是實現此遞歸函數的步驟:

  1. 在開始時,我們將檢查是否到達遞歸的底部或基本情況。 如果要搜索的單詞為空,或者換句話說,如果找到該單詞,則返回true。
  2. 我們通過檢查是否越過網格邊界或當前單元格是否與搜索詞的第一個字符匹配來檢查路徑當前是否有效。
  3. 如果當前步驟有效,則將此單元標記為已訪問。 然後通過為右,下,左和上單元格調用相同的回溯功能來開始探索四個方向。
  4. 最後,我們取消訪問當前單元格並將探索結果返回為true或false。 如果任何子探索的結果為true,則我們從此處返回true,否則返回false。
也可以看看
莫里斯遍歷

履行  

單詞搜索Leetcode解決方案的C ++程序

#include <bits/stdc++.h>
using namespace std;

int row,col;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

bool backtrack(int i,int j,vector<vector<char>>& board, string word,unsigned int ind)
{
    if(ind>=word.size()) return true;
    if(i<0 || i>=row || j<0 || j>=col || board[i][j]!=word[ind]) return false;

    char t=board[i][j];
    board[i][j]= '#';

    for(int k=0;k<4;k++)
    {
        if(backtrack(i+dx[k],j+dy[k],board,word,ind+1))
            return true;
    }
     board[i][j] = t;
    return false;

}

bool exist(vector<vector<char>>& board, string word) 
{
    row= board.size();
    col= board[0].size();

    for(int i=0;i<row;i++)
        for(int j=0;j<col;j++)
            if(backtrack(i,j,board,word,0))
                return true;
    return false;
}

int main() 
{
     vector<vector<char>> board= {
            {'A','B','C','E'},
            {'S','F','C','S'},
            {'A','D','E','E'}
        };
    string word = "ABCCED";
    if(exist(board,word))
        cout<< "true" ;
    else
        cout<< "false" ;
    return 0; 
}
true

單詞搜索Leetcode解決方案的Java程序

class Rextester{
    
  static int row,col;
    static int dx[] = {0, 1, 0, -1};
    static int dy[] = {1, 0, -1, 0};
    
    public static boolean exist(char[][] board, String word)
    {
        row= board.length;
        col= board[0].length;
        
        for(int i=0;i<row;i++)
            for(int j=0;j<col;j++)
                if(backtrack(i,j,board,word,0))
                    return true;
        
        return false;       
    }
    
    static boolean backtrack(int i,int j,char[][] board, String word,int ind)
    {
        if(ind>=word.length()) return true;
        if(i<0 || i>=row || j<0 || j>=col || board[i][j]!=word.charAt(ind)) return false;
        
        char t=board[i][j];
        board[i][j]= '#';
        
        for(int k=0;k<4;k++)
        {
            if(backtrack(i+dx[k],j+dy[k],board,word,ind+1))
                return true;
        }
        
        board[i][j] = t;
        return false;        
    }
    
  public static void main(String args[])
    {
        char[][] board= {
            {'A','B','C','E'},
            {'S','F','C','S'},
            {'A','D','E','E'}
        };
        String word = "ABCCED";
    System.out.println(exist(board,word));
    }
}
true

單詞搜索Leetcode解決方案的複雜度分析  

時間複雜度

O(N *(3 ^ L)): 其中N是網格中單元的總數,L是要搜索的給定單詞的長度。 對於回溯功能,最初我們有4個方向選擇,但由於在上一步中已經訪問了它,因此它減少到3個。 此遞歸函數的深度將等於單詞(L)的長度。 因此,在最壞的情況下,函數調用的總數將是3元樹中的節點數,大約為3 ^​​ L。
在最壞的情況下,我們從N個單元格開始調用此函數。 因此,總體時間複雜度將為O(N *(3 ^ L))。

也可以看看
插入間隔Leetcode解決方案

空間複雜度 

O(長): 其中L是給定單詞的長度。 該空間用於遞歸堆棧。

1