Решење Леетцоде решења за претрагу речи


Ниво тешкоће Средњи
Често питани у амазонка јабука Блоомберг БитеДанце Цисцо еБаи Екпедиа фацебоок Интуит мицрософт пророчанство Пинтерест СервицеНов Снапцхат
Бацктрацкинг матрица

Изјава о проблему

Дали сте мкн таблу и реч, пронађите да ли та реч постоји у мрежи.

Реч се може конструисати од слова суседних ћелија, где су „суседне“ ћелије водоравно или вертикално суседне. Иста словна ћелија не сме се користити више пута.

Пример

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

word = "ABCCED"
true

objašnjenje:

Решење Леетцоде решења за претрагу речи

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

word = "ABCB"
false

Приступ (Бацктрацкинг)

Ово је проблем 2Д преласка мреже, где морамо истражити мрежу како бисмо проверили да ли се дата реч може формирати помоћу суседних ћелија мреже. Али уместо да изводимо ДФС на целом мрежном простору, оптималније бисмо користили метод враћања уназад. У методи повратног пута ићи ћемо само тим путем да бисмо пронашли решење које одговара нашем циљу. Ако у неком тренутку знамо да тренутна путања неће довести до решења, повући ћемо се и ићи на следећи избор.

Обићи ћемо мрежу означавањем тренутне ћелије на нашем путу као посећене у сваком кораку. И на крају сваког корака такође ћемо га одзначити како бисмо могли имати чисто стање да бисмо покушали у другом правцу.

Решење Леетцоде решења за претрагу речи

Алгоритам

Направили бисмо функцију враћања уназад која ће започети са одређеном ћелијом и прећи суседне ћелије мреже на ДФС начин. Будући да дата реч може започети са било ког места у мрежи, заокружили бисмо преко свих ћелија мреже и за сваку ћелију позвали бисмо функцију враћања уназад почев од ове тренутне ћелије.
Како је ова функција враћања уназад а рекурзивни функција, испод су кораци за примену ове рекурзивне функције:

  1. У почетку ћемо проверити да ли смо досегли дно или основни случај рекурзије. Ако је реч коју треба претражити празна или другим речима ако је пронађена, враћамо труе.
  2. Проверавамо да ли је наша путања тренутно важећа или не проверавајући да ли смо прешли границу мреже или се тренутна ћелија подудара са првим знаком речи за претрагу или не.
  3. Ако је тренутни корак важећи, означите ову ћелију као посећену. И почните да истражујете четири смера позивањем исте функције враћања за десну, доњу, леву и горњу ћелију.
  4. На крају поништавамо посету тренутне ћелије и резултате истраживања враћамо као тачне или нетачне. Ако било које од подистраживања резултира тачно, одавде враћамо труе, иначе фалсе.

Имплементација

Ц ++ програм за решење речи Леетцоде за претрагу речи

#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

Јава програм за тражење речи Леетцоде Солутион

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

Анализа сложености решења за тражење речи са Леетцоде-ом

Сложеност времена

О (Н * (3 ^ Л)): где је Н укупан број ћелија у мрежи, а Л је дужина дате речи коју треба претражити. За функцију враћања уназад у почетку добијамо 4 избора за упутства, али даље је смањена на 3, јер смо је већ посетили у претходном кораку. Ова дубина ове рекурзивне функције биће једнака дужини речи (Л). Отуда ће у најгорем случају укупан број позива функције бити број чворова у трокраком стаблу, што је око 3 ^ Л.
У најгорем случају ову функцију називамо почевши од Н броја ћелија. Отуда ће укупна временска сложеност бити О (Н * (3 ^ Л)).

Сложеност простора 

О (Л): где је Л дужина дате речи. Овај простор се користи за рекурзијски стог.