Үг хайх Leetcode шийдэл  


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Амазоны Apple-ийн Bloomberg БайтДанс Cisco Ebay Expedia Facebook-ийн Intuit Microsoft- Oracle-ийн Pinterest ҮйлчилгээNow Snapchat
алгоритмууд Буцах кодлох ярилцлага ярилцлагын бэлтгэл LeetCode LeetCodeSolutions матриц

Асуудлын мэдэгдэл  

Mxn самбар ба үг өгөгдсөн бол уг үг сүлжээнд байгаа эсэхийг олоорой.

Энэ үгийг “зэргэлдээ” эсүүд хэвтээ ба босоо зэргэлдээ орших дараалсан зэргэлдээ нүднүүдийн үсгээс бүтээж болно. Нэг үсэг нүдийг нэгээс илүү удаа ашиглаж болохгүй.

Жишээ нь

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

word = "ABCCED"
true

Тайлбар:

Үг хайх Leetcode шийдэлPin

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

word = "ABCB"
false

Хандалт (буцах зам)  

Энэ бол 2D сүлжээний дамжуулалтын асуудал бөгөөд бид сүлжээг судалж, тухайн үгийг сүлжээний зэргэлдээ нүднүүд ашиглан үүсгэж болох эсэхийг шалгах хэрэгтэй. Гэхдээ DFS-ийг бүхэл бүтэн сүлжээнд ажиллуулахын оронд буцаах аргыг илүү оновчтой ашиглах болно. Буцах арга замаар бид зөвхөн зорилгодоо нийцсэн шийдлийг олохын тулд тэр замаар явах болно. Хэрэв бид одоогийн зам шийдэлд хүргэхгүй гэдгийг хэзээ нэгэн цагт мэдэж байгаа бол ухарч дараагийн сонголт руу явах болно.

Бид алхам тутамд зочилсон замаар одоогийн нүдийг тэмдэглээд торыг тойрон гарах болно. Алхам бүрийн төгсгөлд бид өөр чиглэлийг туршиж үзэхийн тулд цэвэр байдалтай болохын тулд үүнийг тэмдэглэхээ болино.

Үг хайх Leetcode шийдэлPin

Алгоритм  

Бид буцаах функцийг тодорхой нүднээс эхлүүлж, DFS загвараар сүлжээний зэргэлдээ нүднүүдийг дайран өнгөрөх болно. Өгөгдсөн үг нь сүлжээний хаанаас ч эхлэх боломжтой тул бид сүлжээний бүх нүдэн дээр давталт хийж, нүд бүрийн хувьд буцаах функцийг энэ одоогийн нүднээс эхлэн дуудах болно.
Энэхүү ухрах функц нь a рецессив функц, энэ рекурсив функцийг хэрэгжүүлэх алхамуудыг доор харуулав.

  1. Эхэндээ бид доод хэсэгт хүрсэн эсэх эсвэл рекурсын үндсэн тохиолдолд шалгах болно. Хэрэв хайх үг хоосон эсвэл өөрөөр хэлбэл олдсон бол бид үнэн болно.
  2. Бид сүлжээний хил хязгаарыг давсан эсэхийг эсвэл одоогийн нүд нь хайлтын үгийн эхний тэмдэгттэй таарч байгаа эсэхийг шалгах замаар манай зам одоогоор хүчин төгөлдөр байгаа эсэхийг шалгана.
  3. Хэрэв одоогийн алхам хүчинтэй бол энэ нүдийг зочилсон гэж тэмдэглэнэ үү. Дөрвөн чиглэлийг баруун, доош, зүүн, дээш нүдэнд ижил backtracking функцийг дуудаж эхлээрэй.
  4. Эцэст нь бид одоо байгаа нүдэнд зочилж, хайгуулын үр дүнг үнэн, худал гэж буцааж өгдөг. Хэрэв дэд хайгуулын аль нэг нь үр дүнд хүрвэл бид эндээс үнэнийг буцааж, өөрөөр хэлбэл худал гэсэн хариуг өгөх болно.
мөн үзнэ үү
Моррис Траверсал

Хэрэгжүүлэх  

Үг хайх 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

Word Search 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): энд L нь тухайн үгийн урт юм. Энэ зайг рекурсив стек хийхэд ашигладаг.

1