لفظ ڳولڻ Leetcode حل


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ Amazon ايپل Bloomberg ByteDance Cisco eBay Expedia ڪريو سائنسي Microsoft جي Oracle Pinterest سروس 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 گرڊ ٽرانسورس وارو مسئلو آهي ، جتي اسان کي اهو جاچڻ لاءِ گرڊ ڳولڻو آهي ته ڏنل ڏنل گرڊ جي ڀرپاسي خانن کي استعمال ڪندي ڪو لفظ ٺاهي سگهجي ٿو. پر س Dي گرڊ جي جاءِ تي ڊي ايف ايس ڪرڻ بدران اسين وڌيڪ بهتر طريقي سان پٺتي پيل طريقو استعمال ڪندا سين. پوئتي موٽائڻ جو طريقو اسان صرف ان رستي ڏانهن ويندا حل ڳولڻ لاءِ جيڪو اسان جي مقصد سان ملندو آهي. جيڪڏهن اسان ڪنهن موقعي تي knowاڻون ٿا ته هاڻوڪو رستو حل جي طرف نه ٿو وڃي ته پوءِ اسان پوئتي ۽ ايندڙ چونڊ لاءِ وينداسين.

اسان موجوده رستي ۾ موجوده سيل کي نشان لڳل ، گردن جي چوڌاري وينداسين. ۽ هر قدم جي آخر ۾ اسان ان کي غير نشان لڳائينداسون ته اسان ٻئي طرف ڪوشش ڪرڻ لاءِ پاڪ رياست ٿي سگهون.

لفظ ڳولڻ Leetcode حل

الورورٿم

اسان هڪ پٺتي پيل فنڪشن ٺاهينداسين جيڪو هڪ خاص خاني سان شروع ٿيندو ۽ DFS فيشن ۾ گرڊ جي ڀرپاسي واري سيلز کي پار ڪندي. ڇاڪاڻ ته ڏنل لفظ گرڊ مان ڪٿي به شروع ٿي سگهي ٿو ، اسان گرڊ جي سڀني خاني تي لوپ ڪيو ۽ هر هڪ سيل لاءِ اسان هن موجوده سيل کان شروع ٿيندڙ ڪم جي پٺڀرائي سڏيندا.
جئين هي پٺڀرائي ڏيڻ وارو فنڪشن آهي ٻيهر فنڪشن ، هيٺ ڏنل طريقا واري ڪارڪردگي کي لاڳو ڪرڻ جا قدم آهن.

  1. شروعات ۾ اسان جانچ ڪنداسين ته ڇا اسان معاوضي جي هيٺيان يا بنيادي صورت ۾ پهچي چڪا آهيون. جيڪڏهن ڳولا ڪرڻ وارو لفظ خالي آهي يا ٻين لفظن ۾ جيڪڏهن اهو مليو آهي ، اسان سچا موٽون ٿا.
  2. اسان چيڪ ڪريو ته اسان جو رستو في الحال درست آهي يا نه ته چڪاس ڪندي جيڪڏهن اسان گرڊ جي حد پار ڪري چڪا آهيون يا جيڪڏهن موجوده سيل تلاش جي لفظ جي پهرين ڪردار سان ملن ٿا يا نه.
  3. جيڪڏھن اھو موجوده قدم صحيح آھي ته پوءِ ھن سيل جو دورو ڪيو نشان لڳايو. ۽ سا rightي ، هيٺيان ، کاٻي ۽ مٿي جي خانن لاءِ ساڳي پٺتي پائڻ واري فنڪشن کي سڏ ڪري چار طرفن جي ڳولا شروع ڪيو.
  4. آخر ۾ اسان موجوده سيل جو اڻ-دورو ڪيو ۽ صحيح يا غلط جي ڳولا جو نتيجو موٽايو. جيڪڏهن ذيلي ڳولا جو ڪو نتيجو سچ ۾ هوندو ته اسين هتان کان صحيح موٽون ٿا ٻي صورت ۾ غلط واپس اچو.

تي عملدرآمد

ورڊ سرچ ليٽ ڪوڊ حل لاءِ سي ++ پروگرام

#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

جاوا پروگرام ورڊ سرچ لائيٽ ڪوڊ حل لاءِ

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 حل لاءِ پيچيدگي تجزيو

وقت جي پيچيدگي

اي (اين * (3 ^ ايل)): جي جتي گرڊ ۾ N جي سيلن جو ڪل تعداد ۽ ايل آهي ڳولا ٿيڻ لاءِ ڏنل لفظ جي ڊيگهه آهي. پٺتي پيل فنڪشن لاءِ شروعاتي طور تي اسان هدايتون لاءِ 4 چونڊون حاصل ڪيون آهن پر انهي کي 3 تي گهٽايو ويو آهي جيئن ته اسان اڳئين طريقي سان هن کي ڏسي چڪا آهيون. هن recursive فنڪشن جي کوٽائي لفظ جي ڊيگهه جي برابر هوندي (L). انهي ڪري بدترين صورت ۾ مجموعي طور تي ڪتب آڻڻ واري تعداد جو تعداد 3-نرري وڻ ۾ نوڊس جو تعداد هوندو ، جنهن بابت 3 ^ ايل.
بدترين حالت ۾ اسين هن فنڪشن کي N نمبر سيلز کان شروع ڪندي سڏيون ٿا. ان ڪري مجموعي طور تي وقت جي پيچيدگي هوندي O (N * (3 ^ L)).

خلائي پيچيدگي 

اي (ايل): جتي L ڏنل لفظ جي ڊيگهه آهي. ھن جڳھ کي recursion stack لاءِ استعمال ڪيو ويندو آھي.