단어 검색 Leetcode 솔루션  


난이도 중급
자주 묻는 질문 아마존 Apple 블룸버그 게시물에서 ByteDance 시스코 이베이 Expedia 페이스북 서비스 인튜이트 Microsoft 신탁 클립 ServiceNow Snapchat
알고리즘 역 추적 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions 매트릭스

문제 정책  

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

접근 (역 추적)  

이것은 2D 그리드 순회 문제로, 주어진 단어가 그리드의 인접한 셀을 사용하여 형성 될 수 있는지 확인하기 위해 그리드를 탐색해야합니다. 그러나 전체 그리드 공간에서 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-nary 트리의 노드 수이며 약 3 ^ L입니다.
최악의 경우 N 개의 셀부터이 함수를 호출합니다. 따라서 전체 시간 복잡도는 O (N * (3 ^ L))입니다.

참조
간격 Leetcode 솔루션 삽입

공간 복잡성 

O (L) : 여기서 L은 주어진 단어의 길이입니다. 이 공간은 재귀 스택에 사용됩니다.

1