વર્ડ શોધ લેટકોડ સોલ્યુશન


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે એમેઝોન સફરજન બ્લૂમબર્ગ ByteDance સિસ્કો ઇબે એક્સપેડિયા ફેસબુક વધુ વધુ માઈક્રોસોફ્ટ ઓરેકલ Pinterest સેવા હવે Snapchat
બેકટ્રેકીંગ મેટ્રિક્સ

સમસ્યા નિવેદન

એમએક્સએનએન બોર્ડ અને એક શબ્દ આપ્યો, તે શબ્દ ગ્રીડમાં અસ્તિત્વમાં છે કે નહીં તે શોધો.

આ શબ્દ અનુક્રમે અડીને આવેલા કોષોના પત્રોથી બનાવી શકાય છે, જ્યાં “અડીને” કોષો આડા અથવા vertભા પડોશી છે. એક સરખા લેટર સેલનો ઉપયોગ એક કરતા વધુ વાર થઈ શકતો નથી.

ઉદાહરણ

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 ડી ગ્રીડ ટ્ર traવર્સલ સમસ્યા છે, જ્યાં આપેલા શબ્દને ગ્રીડના અડીને કોષોની મદદથી રચના કરી શકાય છે કે કેમ તે તપાસવા આપણે ગ્રીડનું અન્વેષણ કરવું પડશે. પરંતુ સંપૂર્ણ ગ્રીડ જગ્યા પર ડીએફએસ કરવાને બદલે આપણે બેકટ્રેકિંગ પદ્ધતિનો વધુ શ્રેષ્ઠ ઉપયોગ કરીશું. બેકટ્રેકીંગ પદ્ધતિમાં અમે ફક્ત તે જ માર્ગ પર જઈશું કે જે અમારા ઉદ્દેશ સાથે મેળ ખાતો ઉપાય શોધી કા .ે. જો આપણે જાણતા હોઈએ કે હાલનો રસ્તો સમાધાન તરફ દોરી જશે નહીં, તો અમે બેકટ્રેક કરીશું અને આગલી પસંદગી માટે જઈશું.

અમે દરેક પગલાની મુલાકાત લીધા મુજબ અમારા પાથના વર્તમાન સેલને ચિહ્નિત કરીને ગ્રીડની આસપાસ જઈશું. અને દરેક પગલાના અંતે આપણે તેને પણ અનમાર્ક કરીશું જેથી બીજી દિશામાં પ્રયાસ કરવા માટે આપણી પાસે સ્વચ્છ રાજ્ય હોઈ શકે.

વર્ડ શોધ લેટકોડ સોલ્યુશન

અલ્ગોરિધમ

અમે બેકટ્રેકિંગ ફંક્શન બનાવીશું જે કોઈ ચોક્કસ સેલથી શરૂ થશે અને ડીએફએસ ફેશનમાં ગ્રીડના અડીને આવેલા કોષોને ઓળંગી જશે. કારણ કે આપેલ શબ્દ ગ્રીડની કોઈપણ જગ્યાએથી શરૂ થઈ શકે છે, તેથી અમે ગ્રીડના બધા કોષો પર લૂપ લગાવીશું અને દરેક કોષ માટે આપણે આ વર્તમાન કોષથી શરૂ થનારા બેકટ્રેકિંગ ફંક્શનને ક callલ કરીશું.
જેમ કે આ બેકટ્રેકિંગ ફંક્શન એ પુનરાવર્તિત ફંકશન, આ રિકર્સીવ ફંક્શનને અમલમાં મૂકવા માટે નીચે આપેલા પગલાં છે

  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 ^ એલ)): જ્યાં એન એ ગ્રીડના કુલ કોષોની સંખ્યા છે અને L એ આપેલા શબ્દની લંબાઈ છે. બેકટ્રેકિંગ ફંક્શન માટે શરૂઆતમાં આપણને દિશાઓ માટે 4 પસંદગીઓ મળે છે પરંતુ આગળ તે ઘટીને to થઈ ગઈ છે કારણ કે આપણે પહેલાનાં પગલામાં તેની મુલાકાત લીધી છે. આ પુનરાવર્તિત કાર્યની આ depthંડાઈ શબ્દ (એલ) ની લંબાઈ જેટલી હશે. તેથી, ખરાબ કિસ્સામાં, ફંક્શનની નિમણૂકની કુલ સંખ્યા 3-નરી વૃક્ષમાં ગાંઠોની સંખ્યા હશે, જે લગભગ 3 ^ એલ છે.
ખરાબ કિસ્સામાં આપણે કોષોની સંખ્યા N થી શરૂ કરીને આ કાર્યને ક callલ કરીએ છીએ. તેથી એકંદર સમય જટિલતા ઓ (એન * (3 ^ એલ)) હશે.

અવકાશ જટિલતા 

ઓ (એલ): જ્યાં એલ આપેલ શબ્દની લંબાઈ છે. આ જગ્યાનો ઉપયોગ રિકર્ઝન સ્ટેક માટે થાય છે.