शब्द शोध लीटकोड सोल्यूशन


अडचण पातळी मध्यम
वारंवार विचारले ऍमेझॉन सफरचंद ब्लूमबर्ग बाइट डान्स सिस्को हा कोड eBay यामध्ये फेसबुक अंतर्ज्ञानाने जाणणे मायक्रोसॉफ्ट ओरॅकल करा सेवा Snapchat
बॅकट्रॅकिंग मॅट्रिक्स

समस्या विधान

एमएक्सएन बोर्ड आणि शब्द दिल्यास, ग्रीडमध्ये शब्द अस्तित्त्वात आहे का ते शोधा.

हा शब्द अनुक्रमांकाच्या जवळच्या पेशींच्या अक्षरांद्वारे तयार केला जाऊ शकतो, जेथे “समीप” पेशी आडव्या किंवा अनुलंब शेजारी आहेत. समान लेटर सेल एकापेक्षा जास्त वेळा वापरला जाऊ शकत नाही.

उदाहरण

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

अ‍ॅप्रोच (बॅकट्रॅकिंग)

ही एक 2 डी ग्रीड ट्रॅव्हर्सल समस्या आहे, जिथे ग्रीडच्या जवळच्या पेशींचा वापर करुन दिलेला शब्द तयार केला जाऊ शकतो की नाही हे तपासण्यासाठी आपल्याला ग्रीड एक्सप्लोर करावे लागेल. परंतु संपूर्ण ग्रीड जागेवर डीएफएस करण्याऐवजी आम्ही बॅकट्रॅकिंग पद्धत अधिक चांगल्या प्रकारे वापरू. बॅकट्रॅकिंग पद्धतीत आम्ही फक्त त्या मार्गावर जाऊ जे आपल्या उद्देशाशी जुळणारे समाधान शोधण्यासाठी. जर आपल्याला एखाद्या क्षणी माहित असेल की सद्यमार्ग निराकरणाकडे वळत नाही तर आपण मागे वळून पुढच्या निवडीकडे जाऊ.

आम्ही प्रत्येक टप्प्यावर पाहिल्याप्रमाणे आमच्या मार्गावरील विद्यमान सेल चिन्हांकित करून ग्रीडच्या आसपास जाऊ. आणि प्रत्येक चरणानंतर आम्ही त्यास देखील चिन्हांकित करू जेणेकरून दुसरी दिशेने प्रयत्न करण्यासाठी आपल्याकडे स्वच्छ स्थिती असेल.

शब्द शोध लीटकोड सोल्यूशन

अल्गोरिदम

आम्ही एक बॅकट्रॅकिंग फंक्शन बनवू जे एखाद्या विशिष्ट सेलपासून सुरू होईल आणि डीएफएस फॅशनमध्ये ग्रिडच्या जवळच्या पेशींना मागे टाकेल. दिलेला शब्द ग्रीडच्या कोठूनही सुरू होऊ शकतो, म्हणून आम्ही ग्रीडच्या सर्व पेशींवर लूप ठेवू आणि प्रत्येक सेलसाठी या चालू सेलपासून सुरू असलेल्या बॅकट्रॅकिंग फंक्शनला कॉल करू.
कारण हे बॅकट्रॅकिंग फंक्शन आहे रिकर्सिव कार्य, या रिकर्सिव्ह फंक्शनची अंमलबजावणी करण्यासाठी खालील चरण आहेतः

  1. सुरुवातीस आम्ही तपासू की आम्ही पुनरावृत्तीच्या तळाशी पोहोचलो आहोत किंवा बेस केस. शोधला जाणारा शब्द रिकामा असल्यास किंवा दुसर्‍या शब्दात सापडला तर आपण खरा ठरतो.
  2. आम्ही आपला मार्ग सध्या वैध आहे की नाही हे तपासून आम्ही ग्रीडची सीमा पार केली आहे की नाही किंवा वर्तमान सेल शोध शब्दाच्या पहिल्या वर्णांशी जुळत आहे की नाही हे तपासून.
  3. जर सद्य चरण वैध असेल तर या सेलला भेट दिल्याप्रमाणे चिन्हांकित करा. उजव्या, खाली, डाव्या आणि वरच्या सेलसाठी समान बॅकट्रॅकिंग फंक्शन कॉल करून चार दिशांचे अन्वेषण करण्यास प्रारंभ करा.
  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

वर्ड सर्च लीटकोड सोल्यूशनसाठी जटिलता विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन * (3 ^ एल)): जिथे ग्रिडमधील एन एकूण सेलची संख्या आहे आणि एल शोधल्या जाणार्‍या शब्दाची लांबी आहे. बॅकट्रॅकिंग फंक्शनसाठी सुरुवातीला आम्हाला दिशानिर्देशांसाठी 4 पर्याय मिळतात परंतु पुढील 3 चरणांमध्ये आधीपासून भेट दिल्याने ती 3 वर कमी झाली आहे. या रिकर्सीव्ह फंक्शनची ही खोली शब्दाच्या (एल) लांबीच्या समान असेल. म्हणूनच सर्वात वाईट परिस्थितीत फंक्शन आवाहनाची एकूण संख्या 3-नारी झाडाच्या नोडची संख्या असेल, जी सुमारे XNUMX डिग्री एल आहे.
सर्वात वाईट परिस्थितीत आम्ही हे कार्य सेलच्या एन क्रमांकापासून प्रारंभ करतो. म्हणून संपूर्ण वेळ जटिलता ओ (एन * (3 ^ एल)) असेल.

स्पेस कॉम्प्लेक्सिटी 

ओ (एल): जिथे एल दिलेल्या शब्दाची लांबी आहे. ही जागा रिकर्सन स्टॅकसाठी वापरली जाते.