शब्द खोज लेटकोड समाधान  


कठिनाई तह मध्यम
बारम्बार सोधिन्छ अमेजन एप्पल ब्लूमबर्ग बाइटडेन्स सिस्को eBay Expedia फेसबुक Intuit माइक्रोसफ्ट बजेट Pinterest अब सेवा Snapchat
एल्गोरिदम ब्याकट्र्याकिंग कोडिंग अन्तर्वार्ता साक्षात्कार तयारी LeetCode LeetCodeSolutions म्याट्रिक्स

समस्या वक्तव्य  

एक 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

दृष्टिकोण (ब्याट्र्याकिंग)  

यो २ डी ग्रिड ट्रभर्सल समस्या हो, जहाँ हामीले ग्रिडको अन्वेषण गर्नुपर्दछ कि ग्रिडको छेउछाउका कोशाहरूको प्रयोग गरी दिइएको शब्द गठन गर्न सकिन्छ कि भनेर। तर सम्पूर्ण ग्रिड स्पेसमा DFS प्रदर्शन गर्नुको सट्टा हामी अधिक राम्रो ब्याकट्र्याकिंग विधि प्रयोग गर्ने छौं। ब्याकट्र्याकिंग विधिमा हामी केवल त्यो मार्गमा जान्छौं समाधान खोज्न जुन हाम्रो उद्देश्यसँग मेल खान्छ। यदि हामीलाई केहि बिन्दु थाहा छ कि हालको पथले समाधान निम्त्याउँदैन भने हामी पछाडि ट्र्याक गर्छौं र अर्को छनोटको लागि जान्छौं।

हामी प्रत्येक चरणमा भ्रमण गरिएको रूपमा हाम्रो पथमा हालको सेल चिह्नित गरी हामी ग्रिडको वरिपरि जान्छौं। र प्रत्येक चरणको अन्त्यमा हामी यसलाई चिनो हटाउँदछौं ताकि हामीसँग अर्को दिशाको लागि सफा राज्य प्राप्त गर्न सक्दछौं।

शब्द खोज लेटकोड समाधानपिन

अल्गोरिदम  

हामी एक ब्याकट्र्याकि function फंक्शन बनाउँदछौं जुन एउटा खास सेलको साथ सुरू हुन्छ र ग्रिडको नजिकको सेलहरू डीएफएस फेसनमा पार गर्दछ। किनभने दिइएको शब्द ग्रिडको कुनै पनि ठाउँबाट सुरू गर्न सकिन्छ, हामी ग्रिडका सबै सेलहरूमा लुप गर्दछौं र प्रत्येक सेलको लागि हामी यस हालको सेलबाट सुरू हुने ब्याकट्र्याकिंग फंक्शन कल गर्नेछौं।
किनकि यो ब्याकट्र्याकिंग प्रकार्य हो रिकर्सिव प्रकार्य, तल यस रिकर्सिभ प्रकार्य कार्यान्वयन गर्नका लागि चरणहरू छन्:

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

कार्यान्वयन  

C ++ वर्ड सर्च Leetcode समाधानको लागि कार्यक्रम

#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

वर्ड सर्च लीटकोड समाधानको लागि जटिलता विश्लेषण  

समय जटिलता

O (N * (3 ^ L)): जहाँ एन ग्रिडमा सेलहरूको कुल संख्या हो र एल खोज्नु पर्ने शब्दको लम्बाई हो। ब्याकट्र्याकिंग समारोहको लागि हामी सुरुमा directions वटा दिशा निर्देशनहरूको लागि पाउँदछौं तर पछि यो घटेर to मा घट्यो किनकि हामीले अघिल्लो चरणमा यो भ्रमण गरिसकेका छौं। यस पुनरावर्ती प्रकार्यको गहिराई शब्द (L) को लम्बाइ बराबर हुनेछ। तसर्थ, खराब स्थितिमा समारोह आमन्त्रणको कुल संख्या--nree रूखमा नोडहरूको संख्या हुनेछ, जुन करीव ^ ^ L छ।
खराब अवस्थामा हामी यस प्रकार्यलाई N कोषहरूको संख्याबाट शुरू गर्दछौं। तसर्थ समग्र समय जटिलता O (N * (3 ^ L)) हुनेछ।

पनि हेर्नुहोस्
अन्तराल लीटकोड समाधान सम्मिलित गर्नुहोस्

ठाउँ जटिलता 

O (L): जहाँ एल दिइएको शब्दको लम्बाई हो। यो ठाउँ रिकर्सन स्ट्याकको लागि प्रयोग गरिन्छ।

1