Решение Leetcode для поиска слов


Сложный уровень средний
Часто спрашивают в Амазонка Apple Bloomberg ByteDance Cisco eBay Expedia Facebook Постигать интуитивно Microsoft Oracle 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. В конце мы отменяем посещение текущей ячейки и возвращаем результат исследования как истинный или ложный. Если какой-либо из подисследований приводит к истине, мы возвращаем истину отсюда, в противном случае возвращаем ложь.

Реализация

Программа C ++ для решения Leetcode для поиска Word

#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 - длина слова, которое нужно найти. Для функции поиска с возвратом сначала мы получаем 4 варианта направления, но в дальнейшем оно уменьшилось до 3, поскольку мы уже посетили его на предыдущем шаге. Эта глубина этой рекурсивной функции будет равна длине слова (L). Следовательно, в худшем случае общее количество вызовов функции будет равно количеству узлов в 3-ном дереве, что составляет около 3 ^ L.
В худшем случае мы вызываем эту функцию, начиная с N ячеек. Следовательно, общая временная сложность будет O (N * (3 ^ L)).

Космическая сложность 

О (L): где L - длина данного слова. Это пространство используется для стека рекурсии.