단어 검색


난이도 중급
자주 묻는 질문 아마존 Apple 블룸버그 ByteDance 시스코 페이스북 서비스 인튜이트 Microsoft 신탁 ServiceNow Snapchat
배열 역 추적

단어 검색은 우리 삶의 어느 시점에서 단어 찾기 퍼즐과 같은 것입니다. 오늘 나는 테이블에 수정 낱말.

내 독자들은 내가 말하는 것에 대해 약간 당황해야합니다. 더 이상 시간을 낭비하지 않고 문제 진술을하자

단어 검색
단어 검색 줄을 따라 작은 십자말 풀이.

모든 단어를 찾을 수 있습니까?

수직 또는 수평으로 단어를 구성 할 수 있습니다. 인접 단어. 캐치 같은 글자를 다시 사용할 수 없다는 것입니다.

몇 가지 예를 살펴 보겠습니다.

입력 : [[ "A", "B", "C", "E"], [ "S", "F", "C", "S"], [ "A", "D", "E ","이자형"]]

단어 :“ABCB”

출력 : 참

입력 [[ "A", "B", "C", "E"], [ "S", ""F ","C ","S "], ["A ","D ","E ","이자형"]]

단어 :“SEE”

출력 : 참

우리는 무엇을 할 수 있습니까?

다음은 퍼즐에서 단어 검색을 수행하기 위해 따르는 몇 가지 요점입니다.

  • 행렬을 반복하고 첫 글자를 찾은 곳에서 시작합니다.
  • 현재 문자가 cur이되도록하고 다음을 사용하여 문자열을 재귀 적으로 확인합니다. DFS.
  • 단어의 끝에 도달하면 모든 캐릭터를 찾았습니다 매트릭스에서 우리는 참을 돌려 주다
  • 행렬의 각 문자 확인
  • 문자가 단어에 있으면 셀을 살펴보십시오.
    • 수평으로 앞
    • 수평으로 뒤에
    • 수직 위
    • 수직 아래
    • 전화 중 하나라도 true를 반환합니다. 예이! 우리는 단어를 찾았습니다. 더 이상 검색 할 필요가 없습니다.
    • 모든 호출에서 OR 반환
  • 캐릭터를 찾을 수 없으면 반환합니다. 그릇된 
  • 동일한 셀로 계속 돌아 가지 않도록하기 위해 각 셀의 값을 길잃은 문자로 마스킹합니다.

코드 스 니펫의 도움으로 더 잘 이해합시다

단어 검색 용 Java 코드

class Solution
{
    boolean trav(char[][] board,int cur,int i,int j,String word)
    {
       //If we have found all the characters
       if(cur>=word.length())
            return true;
       //In case the character does not match/we go out of the board
       if(i<0 || j<0 || i>=board.length || j>=board[i].length || 
          board[i][j]!=word.charAt(cur))
            return false;
        //Masking our board to prevent repetitive calls
        char temp=board[i][j];
        board[i][j]='*';
        boolean ans=(trav(board,cur+1,i+1,j,word) || trav(board,cur+1,i,j+1,word)
                     || trav(board,cur+1,i-1,j,word) || trav(board,cur+1,i,j-1,word));
        board[i][j]=temp;
            return ans;   
    }
    public boolean exist(char[][] board, String word) 
    {
        boolean ans=false;
        for(int i=0;i<board.length;i++)
        {
            for(int j=0;j<board[i].length;j++)
            {
                //We start checking from where we find the first character
                if(board[i][j]==word.charAt(0) && trav(board,0,i,j,word))
                {
                    return true;
                }
            }
        }
        return false;
    }
}

단어 검색을위한 C ++ 코드

{
public:
    bool trav(vector<vector<char>>& board,int cur,int i,int j,string word)
    {
       if(cur>=word.length())
            return true;
       if(i<0 || j<0 || i>=board.size() || j>=board[i].size() || 
          board[i][j]!=word[cur])
            return false;
        char temp=board[i][j];
        board[i][j]='*';
        bool ans=(trav(board,cur+1,i+1,j,word) || trav(board,cur+1,i,j+1,word)
                     || trav(board,cur+1,i-1,j,word) || trav(board,cur+1,i,j-1,word));
        board[i][j]=temp;
            return ans;   
    }
public:
    bool exist(vector<vector<char>>& board, string word)
    {
     for(int i=0;i<board.size();i++)
     {
     for(int j=0;j<board[i].size();j++)
     {
     if(board[i][j]==word[0] && trav(board,0,i,j,word))
     {
     return true;
     }
     }
     }
    return false;   
    }
};
[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]

ABCB
true

복잡성 분석

시간 복잡도 : O (m * n * l)

어디에,

m = 행렬의 길이

n = 행렬의 폭

l = 단어 찾기 문제에서 주어진 단어의 길이.

어떻게?

  • 제공된 단어의 첫 글자를 찾으려고 전체 보드를 탐색합니다.
    • 최악의 경우 첫 번째 문자를 누르지 않고 전체 보드를 횡단 할 수 있습니다.
    • 그런 다음 다음 문자를 누를 때까지 근처 문자를 검색합니다.
      • 따라서 우리는 전체 단어를 횡단합니다.
      • 그렇게하는 시간 복잡도 = O (L)
    • 이 O (L) 연산은 O (M)의 외부 루프에서 매번 호출 될 수 있습니다. 지금까지 시간을 복잡하게 만들기 O (M * L)
  • 위의 작업은 O (N) 루프에서 실행됩니다.
  • 세 개의 루프가 함께 모여 시간 복잡도 = O (M * N * L)