शब्द खोज Leetcode समाधान  


कठिनाई स्तर मध्यम
में अक्सर पूछा वीरांगना सेब ब्लूमबर्ग ByteDance सिस्को ईबे Expedia Facebook सहज माइक्रोसॉफ्ट ओरेकल 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

दृष्टिकोण (पीछे हटना)  

यह एक 2 डी ग्रिड ट्रैवर्सल समस्या है, जहां हमें ग्रिड की जांच करना है कि क्या ग्रिड के आसन्न कोशिकाओं का उपयोग करके दिए गए शब्द का गठन किया जा सकता है। लेकिन पूरे ग्रिड स्पेस पर डीएफएस करने के बजाय हम अधिक बेहतर तरीके से बैकट्रैकिंग विधि का उपयोग करेंगे। बैकट्रैकिंग विधि में हम केवल उस रास्ते पर जाएंगे जिसका समाधान हमारे उद्देश्य से मेल खाता है। यदि हम किसी बिंदु पर जानते हैं कि वर्तमान पथ समाधान की ओर नहीं ले जाएगा, तो हम पीछे हटेंगे और अगली पसंद के लिए जाएंगे।

हम अपने रास्ते में वर्तमान सेल को चिह्नित करके ग्रिड के चारों ओर जाएंगे, जैसा कि प्रत्येक चरण पर देखा गया है। और प्रत्येक चरण के अंत में हम इसे भी अनमार्क कर देंगे ताकि दूसरी दिशा में प्रयास करने के लिए हमारे पास एक स्वच्छ राज्य हो सके।

शब्द खोज Leetcode समाधानपिन

कलन विधि  

हम एक बैकट्रैकिंग फंक्शन करेंगे जो एक विशेष सेल के साथ शुरू होगा और डीएफएस फैशन में ग्रिड के आसन्न कोशिकाओं को पीछे ले जाएगा। क्योंकि दिए गए शब्द ग्रिड में कहीं से भी शुरू हो सकते हैं, हम ग्रिड की सभी कोशिकाओं पर लूप करेंगे और प्रत्येक सेल के लिए हम इस वर्तमान सेल से शुरू होने वाले बैकट्रैकिंग फंक्शन को कॉल करेंगे।
के रूप में इस backtracking समारोह एक है पुनरावर्ती फ़ंक्शन, नीचे इस पुनरावर्ती फ़ंक्शन को लागू करने के लिए चरण हैं:

  1. शुरुआत में हम जाँच करेंगे कि क्या हम नीचे या बेस केस की पुनरावृत्ति तक पहुँच गए हैं। यदि खोजा जाने वाला शब्द खाली है या अन्य शब्दों में यदि यह पाया जाता है, तो हम सच होते हैं।
  2. हम जाँचते हैं कि क्या हमारा रास्ता वर्तमान में वैध है या नहीं, यह जाँचने से कि क्या हमने ग्रिड की सीमा पार कर ली है या यदि वर्तमान सेल खोज शब्द के पहले वर्ण से मेल खाता है या नहीं।
  3. यदि वर्तमान चरण मान्य है, तो इस सेल पर जाएँ के रूप में चिह्नित करें। और दाएं, नीचे, बाएं और ऊपर की कोशिकाओं के लिए एक ही बैकड्रैकिंग फ़ंक्शन को कॉल करके चार दिशाओं की खोज शुरू करें।
  4. अंत में हम वर्तमान सेल पर अन-विजिट करते हैं और अन्वेषण के परिणाम को सही या गलत मानते हैं। यदि कोई उप अन्वेषण सत्य में परिणत होता है तो हम यहाँ से सच लौटाते हैं अन्यथा झूठे वापस लौटते हैं।
यह भी देखें
मॉरिस ट्रैवर्सल

कार्यान्वयन  

वर्ड सर्च लेटकोड सॉल्यूशन के लिए C ++ प्रोग्राम

#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 समाधान के लिए जटिलता विश्लेषण  

समय जटिलता

O (N * (3 ^ L)): जहां N ग्रिड में कोशिकाओं की कुल संख्या है और L को खोजे जाने वाले शब्द की लंबाई है। शुरू में बैकग्राउंडिंग फंक्शन के लिए हमें दिशा-निर्देश के लिए 4 विकल्प मिलते हैं लेकिन आगे यह घटकर 3 हो जाता है क्योंकि हम पहले ही इसे पिछले चरण में देख चुके हैं। इस पुनरावर्ती फ़ंक्शन की गहराई शब्द (एल) की लंबाई के बराबर होगी। इसलिए सबसे खराब स्थिति में फ़ंक्शन इनवोकेशन की कुल संख्या 3-नेरी ट्री में नोड्स की संख्या होगी, जो लगभग 3 ^ एल है।
सबसे खराब स्थिति में हम इस फ़ंक्शन को एन संख्या की कोशिकाओं से शुरू करते हैं। इसलिए समग्र समय जटिलता O (N * (3 ^ L)) होगी।

यह भी देखें
अंतराल Leetcode समाधान डालें

अंतरिक्ष जटिलता 

O (L): जहाँ L दिए गए शब्द की लंबाई है। इस जगह का उपयोग रिकर्सन स्टैक के लिए किया जाता है।

1