Решение на Leetcode за търсене на думи


Ниво на трудност M
Често задавани в Амазонка ябълка Bloomberg ByteDance Cisco иБей Expedia Facebook Intuit 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

Подход (Backtracking)

Това е проблем за двуизмерно обхождане на мрежата, където трябва да изследваме мрежата, за да проверим дали дадената дума може да се формира с помощта на съседни клетки на мрежата. Но вместо да изпълняваме DFS върху цялото пространство на мрежата, ние по-оптимално бихме използвали метода за обратно проследяване. В метода на обратното проследяване ще отидем само по този път, за да намерим решението, което отговаря на нашата цел. Ако в даден момент знаем, че текущият път няма да доведе до решението, тогава ще се върнем назад и ще преминем към следващия избор.

Ще заобиколим мрежата, като маркираме текущата клетка по нашия път, посетена на всяка стъпка. И в края на всяка стъпка също ще я демаркираме, за да можем да имаме чисто състояние, за да опитаме друга посока.

Решение на Leetcode за търсене на думи

алгоритъм

Бихме направили функция за проследяване, която ще започне с определена клетка и ще прекоси съседните клетки на мрежата по DFS. Тъй като дадената дума може да започне от всяко място в мрежата, ние бихме се завъртали над всички клетки на мрежата и за всяка клетка ще извикаме функцията за проследяване, започвайки от тази текуща клетка.
Тъй като тази функция за проследяване е a рекурсивни функция, по-долу са стъпките за прилагане на тази рекурсивна функция:

  1. В началото ще проверим дали сме стигнали до дъното или основния случай на рекурсията. Ако думата, която трябва да се търси, е празна или с други думи, ако е намерена, ние връщаме true.
  2. Проверяваме дали пътят ни в момента е валиден или не, като проверяваме дали сме преминали границата на мрежата или дали текущата клетка съвпада с първия символ на думата за търсене или не.
  3. Ако текущата стъпка е валидна, маркирайте тази клетка като посетена. И започнете да изследвате четирите посоки, като извикате една и съща функция за обратно проследяване за клетките надясно, надолу, наляво и нагоре.
  4. Накрая премахваме посещението на текущата клетка и връщаме резултата от изследването като вярно или невярно. Ако някое от подпроучването доведе до true, ние връщаме true от тук, в противен случай връщаме false.

изпълнение

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

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)).

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

O (L): където L е дължината на дадената дума. Това пространство се използва за стека на рекурсия.