വേഡ് തിരയൽ ലീറ്റ്കോഡ് പരിഹാരം


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു ആമസോൺ ആപ്പിൾ ബ്ലൂംബർഗ് ബൈറ്റ്ഡാൻസ് സിസ്കോ ബെ ബൈ ഫേസ്ബുക്ക് Intuit മൈക്രോസോഫ്റ്റ് ഒറാക്കിൾ പോസ്റ്റ് സർവീസ് ഇപ്പോൾ 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

സമീപനം (ബാക്ക്‌ട്രാക്കിംഗ്)

ഇതൊരു 2 ഡി ഗ്രിഡ് ട്രാവെർസൽ പ്രശ്‌നമാണ്, ഇവിടെ ഗ്രിഡിന്റെ അടുത്തുള്ള സെല്ലുകൾ ഉപയോഗിച്ച് തന്നിരിക്കുന്ന വാക്ക് രൂപപ്പെടുത്താൻ കഴിയുമോ എന്ന് പരിശോധിക്കാൻ ഞങ്ങൾ ഗ്രിഡ് പര്യവേക്ഷണം ചെയ്യണം. മുഴുവൻ ഗ്രിഡ് സ്ഥലത്തും ഡി‌എഫ്‌എസ് നടത്തുന്നതിനുപകരം ഞങ്ങൾ‌ ബാക്ക്‌ട്രാക്കിംഗ് രീതി കൂടുതൽ‌ ഉപയോഗിക്കും. ബാക്ക്‌ട്രാക്കിംഗ് രീതിയിൽ, ഞങ്ങളുടെ ലക്ഷ്യവുമായി പൊരുത്തപ്പെടുന്ന പരിഹാരം കണ്ടെത്താൻ ഞങ്ങൾ ആ പാതയിലേക്ക് പോകും. നിലവിലെ പാത പരിഹാരത്തിലേക്ക് നയിക്കില്ലെന്ന് ചില ഘട്ടങ്ങളിൽ നമുക്കറിയാമെങ്കിൽ, ഞങ്ങൾ ബാക്ക്ട്രാക്ക് ചെയ്ത് അടുത്ത ചോയിസിലേക്ക് പോകും.

ഓരോ ഘട്ടത്തിലും സന്ദർശിച്ചതുപോലെ ഞങ്ങളുടെ പാതയിലെ നിലവിലെ സെൽ അടയാളപ്പെടുത്തി ഞങ്ങൾ ഗ്രിഡിന് ചുറ്റും പോകും. ഓരോ ഘട്ടത്തിൻറെയും അവസാനത്തിൽ‌ ഞങ്ങൾ‌ അതിനെ അടയാളപ്പെടുത്തും, അതിനാൽ‌ മറ്റൊരു ദിശ പരീക്ഷിക്കാൻ‌ ഞങ്ങൾ‌ക്ക് ശുദ്ധമായ അവസ്ഥ ഉണ്ടായിരിക്കും.

വേഡ് തിരയൽ ലീറ്റ്കോഡ് പരിഹാരം

അൽഗോരിതം

ഞങ്ങൾ ഒരു ബാക്ക്ട്രാക്കിംഗ് ഫംഗ്ഷൻ നടത്തും, അത് ഒരു പ്രത്യേക സെല്ലിൽ നിന്ന് ആരംഭിച്ച് ഗ്രിഡിന്റെ അടുത്തുള്ള സെല്ലുകൾ 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)) ആയിരിക്കും.

ബഹിരാകാശ സങ്കീർണ്ണത 

O (L): ഇവിടെ L എന്നത് തന്നിരിക്കുന്ന പദത്തിന്റെ നീളം. ഈ ഇടം ആവർത്തന സ്റ്റാക്കിനായി ഉപയോഗിക്കുന്നു.