Рашэнне Leetcode для пошуку слоў


Узровень складанасці серада
Часта пытаюцца ў амазонка яблык Bloomberg ByteDance Cisco eBay Expedia facebook Спасцігаць інтуітыўна Microsoft Аракул Pinterest ServiceNow Snapchat
Фанаграмы матрыца

Пастаноўка праблемы

З улікам дошкі 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 адсюль, інакш вяртаем false.

Рэалізацыя

Праграма 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

Праграма 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

Аналіз складанасці для рашэння для пошуку слоў з выкарыстаннем леэт-кода

Складанасць часу

O (N * (3 ^ L)): дзе N - агульная колькасць вочак у сетцы, а L - даўжыня дадзенага слова, якое трэба шукаць. Для функцыі зваротнага адсочвання першапачаткова мы атрымліваем 4 варыянты ўказанняў, але далей яна зменшылася да 3, бо мы ўжо наведвалі яе на папярэднім этапе. Глыбіня гэтай рэкурсіўнай функцыі будзе роўная даўжыні слова (L). Такім чынам, у горшым выпадку агульная колькасць выкліку функцыі будзе колькасцю вузлоў у 3-нарысным дрэве, што складае каля 3 ^ L.
У горшым выпадку мы называем гэтую функцыю, пачынаючы з N колькасці клетак. Такім чынам, агульная складанасць часу будзе O (N * (3 ^ L)).

Касмічная складанасць 

O (L): дзе L - даўжыня дадзенага слова. Гэта прастора выкарыстоўваецца для стэка рэкурсіі.