వర్డ్ సెర్చ్ లీట్‌కోడ్ సొల్యూషన్


కఠినత స్థాయి మీడియం
తరచుగా అడుగుతుంది అమెజాన్ ఆపిల్ బ్లూమ్బెర్గ్ ByteDance సిస్కో eBay Expedia ద్వారా <span style="font-family: Mandali; ">ఫేస్‌బుక్ </span> Intuit మైక్రోసాఫ్ట్ ఒరాకిల్ Pinterest 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 చేయటానికి బదులుగా మేము బ్యాక్‌ట్రాకింగ్ పద్ధతిని మరింత అనుకూలంగా ఉపయోగిస్తాము. బ్యాక్‌ట్రాకింగ్ పద్ధతిలో మన లక్ష్యానికి సరిపోయే పరిష్కారాన్ని కనుగొనడానికి మాత్రమే మేము ఆ మార్గానికి వెళ్తాము. ప్రస్తుత మార్గం పరిష్కారానికి దారితీయదని మనకు ఏదో ఒక సమయంలో తెలిస్తే, మనం బ్యాక్‌ట్రాక్ చేసి తదుపరి ఎంపిక కోసం వెళ్తాము.

ప్రతి దశలో సందర్శించినట్లుగా మా మార్గంలో ప్రస్తుత కణాన్ని గుర్తించడం ద్వారా మేము గ్రిడ్ చుట్టూ వెళ్తాము. మరియు ప్రతి దశ చివరలో మేము దానిని కూడా గుర్తు పెడతాము, తద్వారా మరొక దిశను ప్రయత్నించడానికి మనకు స్వచ్ఛమైన స్థితి ఉంటుంది.

వర్డ్ సెర్చ్ లీట్‌కోడ్ సొల్యూషన్

అల్గారిథం

మేము బ్యాక్‌ట్రాకింగ్ ఫంక్షన్‌ను చేస్తాము, ఇది ఒక నిర్దిష్ట సెల్‌తో ప్రారంభమవుతుంది మరియు DFS పద్ధతిలో గ్రిడ్ యొక్క ప్రక్కన ఉన్న కణాలను దాటుతుంది. ఇచ్చిన పదం గ్రిడ్‌లోని ఎక్కడి నుండైనా ప్రారంభించవచ్చు కాబట్టి, మేము గ్రిడ్‌లోని అన్ని కణాలపై లూప్ చేస్తాము మరియు ప్రతి సెల్ కోసం ఈ ప్రస్తుత సెల్ నుండి ప్రారంభమయ్యే బ్యాక్‌ట్రాకింగ్ ఫంక్షన్‌ను పిలుస్తాము.
ఈ బ్యాక్‌ట్రాకింగ్ ఫంక్షన్ a పునరావృత ఫంక్షన్, ఈ పునరావృత ఫంక్షన్‌ను అమలు చేయడానికి దశలు క్రింద ఉన్నాయి:

  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

వర్డ్ సెర్చ్ లీట్‌కోడ్ సొల్యూషన్ కోసం సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

O (N * (3 ^ L)): ఇక్కడ N అనేది గ్రిడ్‌లోని మొత్తం కణాల సంఖ్య మరియు L అనేది శోధించాల్సిన పదం యొక్క పొడవు. బ్యాక్‌ట్రాకింగ్ ఫంక్షన్ కోసం మొదట్లో మనకు దిశల కోసం 4 ఎంపికలు లభిస్తాయి, అయితే మునుపటి దశలో మేము ఇప్పటికే సందర్శించినందున ఇది 3 కి తగ్గింది. ఈ పునరావృత ఫంక్షన్ యొక్క లోతు పదం (L) యొక్క పొడవుకు సమానంగా ఉంటుంది. అందువల్ల చెత్త సందర్భంలో మొత్తం ఫంక్షన్ ఆహ్వానం 3-నారీ చెట్టులోని నోడ్‌ల సంఖ్య అవుతుంది, ఇది సుమారు 3 ^ L.
చెత్త సందర్భంలో మేము ఈ ఫంక్షన్‌ను N సంఖ్య కణాల నుండి ప్రారంభిస్తాము. అందువల్ల మొత్తం సమయ సంక్లిష్టత O (N * (3 ^ L)) అవుతుంది.

అంతరిక్ష సంక్లిష్టత 

ఓ (ఎల్): ఇక్కడ L అనేది ఇచ్చిన పదం యొక్క పొడవు. ఈ స్థలం పునరావృత స్టాక్ కోసం ఉపయోగించబడుతుంది.