Ҷустуҷӯи калимаи Leetcode  


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Amazon себ Блумберг ByteDance Cisco мехаранд Expedia Facebook Шабака Microsoft Oracle ба дӯстат ServiceNow Snapchat
алгоритмҳо Бозгашт рамзгузорӣ мусоҳиба омодасозии мусоҳиба LeetCode LeetCodeSolutions 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

Равиш (Backtracking)  

Ин масъалаи гардиши шабакаи 2D мебошад, ки мо бояд шабакаро омӯхта, санҷем, ки оё калимаи додашуда бо истифода аз ҳуҷайраҳои шафати шабака сохта шуданаш мумкин аст. Аммо ба ҷои иҷрои DFS дар фазои тамоми шабака, мо усули ақибнишиниро оптималӣтар истифода хоҳем кард. Дар усули бозгашт мо танҳо ба он роҳ меравем, то роҳи ҳалли ба ҳадафи мо мувофиқро ёбем. Агар мо ягон вақт медонем, ки роҳи ҳозира боиси ҳалли масъала нахоҳад шуд, пас мо ақибнишинӣ карда, ба интихоби оянда хоҳем рафт.

Мо бо нишон додани ячейкаи ҳозираи роҳи худ, ки дар ҳар қадам ташриф овардаем, гирди шабакаро давр мезанем. Ва дар охири ҳар як қадам мо онро аломатгузорӣ хоҳем кард, то ки мо як давлати тоза дошта бошем, то самти дигареро санҷем.

Ҷустуҷӯи калимаи Leetcode

Алгоритм  

Мо функсияи баргаштанро иҷро мекардем, ки он бо як ячейкаи мушаххас оғоз ёфта, ҳуҷайраҳои шафати шабакаро ба тарзи DFS убур кунад. Азбаски калимаи додашуда метавонад аз ҷои дилхоҳ дар шабака сар шавад, мо ҳамаи чашмакҳои шабакаро давр мезанем ва барои ҳар як ячейка функсияи бозгаштро аз ин чашмаки ҷорӣ меномем.
Тавре ки ин функсияи backtracking як аст рекурсивӣ функсия, дар зер қадамҳои татбиқи ин функсияи рекурсивӣ оварда шудаанд:

  1. Дар аввал мо тафтиш хоҳем кард, ки мо ба поён расидем ё ҳолати асосии рекурсия. Агар калимаи ҷустуҷӯшаванда холӣ бошад ё ба ибораи дигар, агар он пайдо шавад, мо ҳақиқӣ бармегардем.
  2. Мо месанҷем, ки роҳи мо дар айни замон дуруст аст ё не, бо санҷидани он ки мо сарҳади шабакаро убур кардаем ё ячейкаи ҷорӣ ба аломати якуми калимаи ҷустуҷӯ мувофиқат мекунад ё не.
  3. Агар қадами ҷорӣ дуруст бошад, пас ин чашмакро ҳамчун ташриф қайд кунед. Ва омӯхтани чаҳор самтро бо занг задан ба ҳамон функсияи бозгашт барои ҳуҷайраҳои рост, поён, чап ва боло оғоз кунед.
  4. Дар охир мо ба ячейкаи ҳозира ташриф намеорем ва натиҷаи таҳқиқотро рост ё дурӯғ бармегардонем. Агар ягонтои иктишофӣ натиҷа диҳад, пас мо ҳақиқиро аз ин ҷо бармегардем, дар акси ҳол бардурӯғ бармегарданд
ҳамчунин нигаред
Моррис Траверсал

татбиќи  

Барномаи 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  

Мураккабии вақт

O (N * (3 ^ L)): ки дар он N шумораи умумии чашмакҳо дар шабака ва L дарозии калимаи додашуда барои ҷустуҷӯ мебошад. Барои функсияи backtracking дар аввал мо 4 интихобро барои самтҳо мегирем, аммо минбаъд он ба 3 кам шуд, зеро мо аллакай дар қадами гузашта дидан карда будем. Ин амиқи ин функсияи рекурсивӣ ба дарозии калима (L) баробар хоҳад буд. Аз ин рӯ, дар бадтарин ҳолат шумораи умумии даъвати функсия шумораи гиреҳҳои дарахти 3-нарӣ хоҳад буд, ки тақрибан 3 ^ L мебошад.
Дар бадтарин ҳолат, мо ин функсияро аз шумораи N чашмакҳо сар мекунем. Аз ин рӯ, мураккабии умумии вақт O (N * (3 ^ L)) хоҳад буд.

ҳамчунин нигаред
Вориди ҳалли Leetcode фосилаи

Мураккабии фазо 

O (L): ки дар он L дарозии калимаи додашуда мебошад. Ин фосила барои стеки рекурсионӣ истифода мешавад.