单词搜索Leetcode解决方案


难度级别 中等
经常问 亚马逊 Apple 彭博 ByteDance 思科 易趣 Expedia的 Facebook 意会 微软 神谕 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))。

空间复杂度 

O(长): 其中L是给定单词的长度。 该空间用于递归堆栈。