Բառի որոնում Leetcode լուծում


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Amazon խնձոր Bloomberg ByteDance Cisco eBay Expedia facebook Intuit Microsoft Պատգամախոս Pinterest ServiceNow- ը Snapchat
Հետադարձ կապ Matrix

Խնդիրի հայտարարություն

Հաշվի առնելով 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. Սկզբում մենք ստուգելու ենք, արդյոք հասել ենք հետադարձի ներքևի՞ն, թե՞ հիմնական դեպքին: Եթե ​​որոնվող բառը դատարկ է կամ այլ կերպ ասած, եթե այն գտնվել է, մենք վերադառնում ենք իրական:
  2. Մենք ստուգում ենք ՝ մեր ուղին ներկայումս վավեր է, թե ոչ, ստուգելով ՝ մենք անցե՞լ ենք ցանցի սահմանը, թե՞ ներկայիս բջիջը համապատասխանում է որոնման բառի առաջին նիշին, թե ոչ:
  3. Եթե ​​ընթացիկ քայլը վավեր է, ապա այս բջիջը նշեք որպես այցելված: Եվ սկսեք ուսումնասիրել չորս ուղղությունները ՝ զանգահարելով նույն հետադարձման գործառույթը աջ, ներքև, ձախ և վերև բջիջների համար:
  4. Վերջում մենք այցելում ենք ներկա բջիջ և հետ բերում հետազոտության արդյունքը որպես ճշմարիտ կամ կեղծ: Եթե ​​ենթահետազոտություններից որևէ մեկը ճշմարիտ է, ապա մենք այստեղից վերադառնում ենք true, հակառակ դեպքում կեղծ ենք վերադառնում:

Իրականացման

C ++ ծրագիր Բառի որոնման Leetcode լուծման համար

#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

Java ծրագիր բառերի որոնման համար Leetcode լուծման համար

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 լուծման համար

Timeամանակի բարդություն

O (N * (3 ^ L)): որտեղ N- ը ցանցում բջիջների ընդհանուր թիվն է, իսկ L- ը `որոնվող տվյալ բառի երկարությունը: Հետադարձ կապի գործառույթի համար սկզբնական շրջանում մենք ստանում ենք 4 ընտրություն ուղղությունների համար, բայց այն հետագայում այն ​​կրճատվում է և հասնում 3-ի, քանի որ նախորդ քայլում արդեն այցելել էինք այն: Այս ռեկուրսիվ գործառույթի այս խորությունը հավասար կլինի բառի երկարությանը (L): Հետևաբար, վատագույն դեպքում գործառույթի կանչման ընդհանուր քանակը կլինի 3-նանոց ծառի հանգույցների քանակը, որը կազմում է մոտ 3 ^ L:
Ամենավատ դեպքում մենք այս ֆունկցիան անվանում ենք սկսած N թվով բջիջներից: Հետևաբար, ընդհանուր ժամանակի բարդությունը կլինի O (N * (3 ^ L)):

Տիեզերական բարդություն 

O (L): որտեղ L տրված բառի երկարությունն է: Այս տարածությունն օգտագործվում է հետադարձ կապի համար: