راه حل کد جستجو


سطح دشواری متوسط
اغلب در آمازون سیب بلومبرگ ByteDance سیسکو ای بی Expedia فیس بوک تعلیم دادن مایکروسافت وحی پینترست ServiceNow Snapchat
عقب نشینی ماتریس

بیان مسأله

با توجه به یک صفحه mxn و یک کلمه ، اگر این کلمه در شبکه وجود دارد را پیدا کنید.

این کلمه را می توان از حروف سلولهای مجاور متوالی ساخت ، جایی که سلولهای "مجاور" به طور افقی یا عمودی همسایه هستند. ممکن است از یک سلول حرف بیش از یک بار استفاده نشود.

مثال

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

word = "ABCCED"
true

شرح:

راه حل کد جستجو

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

word = "ABCB"
false

رویکرد (بازگشت به مرحله)

این یک مسئله پیمایش شبکه 2D است ، جایی که ما باید شبکه را بررسی کنیم تا بررسی کنیم آیا کلمه داده شده می تواند با استفاده از سلولهای مجاور شبکه تشکیل شود. اما به جای اجرای DFS در کل فضای شبکه ، ما بهینه تر از روش backtracking استفاده می کنیم. در روش backtracking ما فقط برای یافتن راه حلی که با هدف ما مطابقت دارد به آن مسیر می رویم. اگر در برهه ای بدانیم که مسیر فعلی به راه حلی منجر نخواهد شد ، ما عقب نشینی کرده و به دنبال انتخاب بعدی خواهیم رفت.

ما با علامت گذاری سلول فعلی در مسیر خود به عنوان بازدید شده در هر مرحله ، شبکه را دور خواهیم زد. و در پایان هر مرحله نیز آن را علامت گذاری می کنیم تا بتوانیم حالت تمیزی داشته باشیم تا جهت دیگری را امتحان کنیم.

راه حل کد جستجو

الگوریتم

ما یک عملکرد برگشتی ایجاد می کنیم که با یک سلول خاص شروع می شود و سلول های مجاور شبکه را به صورت DFS عبور می دهد. از آنجا که کلمه داده شده می تواند از هر نقطه از شبکه شروع شود ، ما تمام سلول های شبکه را حلقه می کنیم و برای هر سلول ما عملکرد برگشتی را از این سلول فعلی فراخوانی خواهیم کرد.
همانطور که این عملکرد برگشتی یک است بازگشتی در زیر مراحل اجرای این تابع بازگشتی وجود دارد:

  1. در ابتدا بررسی خواهیم کرد که آیا به پایین یا حالت اصلی بازگشت رسیده ایم. اگر کلمه مورد جستجو خالی باشد یا به عبارت دیگر اگر پیدا شده باشد ، درست برمی گردیم.
  2. با بررسی اینکه از مرز شبکه عبور کرده ایم یا اینکه سلول فعلی با شخصیت اول کلمه جستجو مطابقت دارد یا خیر ، بررسی می کنیم که آیا مسیر ما در حال حاضر معتبر است یا خیر.
  3. اگر مرحله فعلی معتبر است ، این سلول را به عنوان بازدید شده علامت گذاری کنید. و کاوش چهار جهت را با فراخوانی همان عملکرد برگشت برای سلولهای راست ، پایین ، چپ و بالا شروع کنید.
  4. در پایان ما از سلول فعلی بازدید نمی کنیم و نتیجه کاوش را درست یا غلط برمی گردانیم. اگر هر یک از زیر کاوش ها به درست منجر شود ، ما از اینجا درست برمی گردیم در غیر این صورت نادرست برمی گردیم.

پیاده سازی

برنامه C ++ برای جستجوی کلمه Leetcode Solution

#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

برنامه جاوا برای جستجوی کلمه 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

تجزیه و تحلیل پیچیدگی برای جستجوی کلمه راه حل کد

پیچیدگی زمان

O (N * (3 ^ L)): که در آن N تعداد کل سلولهای شبکه و L طول کلمه داده شده برای جستجو است. برای عملکرد backtracking در ابتدا ما 4 گزینه برای مسیرها پیدا می کنیم اما بعداً به 3 کاهش یافت ، زیرا قبلاً در مرحله قبل از آن بازدید کرده ایم. این عمق این تابع بازگشتی برابر با طول کلمه (L) خواهد بود. بنابراین در بدترین حالت تعداد کل فراخوانی عملکرد تعداد گره های درخت 3-nary خواهد بود که حدود 3 ^ L است.
در بدترین حالت ما این تابع را از تعداد سلول N شروع می کنیم. بنابراین پیچیدگی کلی زمان O (N * (3 ^ L)) خواهد بود.

پیچیدگی فضا 

O (L): جایی که L طول کلمه داده شده است. این فضا برای پشته بازگشتی استفاده می شود.