சொல் தேடல் லீட்கோட் தீர்வு


சிரமம் நிலை நடுத்தர
அடிக்கடி கேட்கப்படுகிறது அமேசான் ஆப்பிள் ப்ளூம்பெர்க் ByteDance சிஸ்கோ ஈபே Expedia பேஸ்புக் intuit மைக்ரோசாப்ட் ஆரக்கிள் இடுகைகள் 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

அணுகுமுறை (பின் தடமறிதல்)

இது 2 டி கட்டம் குறுக்குவெட்டு சிக்கலாகும், அங்கு கட்டத்தின் அருகிலுள்ள கலங்களைப் பயன்படுத்தி கொடுக்கப்பட்ட வார்த்தையை உருவாக்க முடியுமா என்பதை அறிய கட்டத்தை ஆராய வேண்டும். ஆனால் முழு கட்ட இடத்திலும் டி.எஃப்.எஸ் செய்வதற்கு பதிலாக, நாங்கள் பின்வாங்கல் முறையைப் பயன்படுத்துவோம். பின்வாங்கல் முறையில், எங்கள் நோக்கத்துடன் பொருந்தக்கூடிய தீர்வைக் கண்டறிய மட்டுமே நாங்கள் அந்த பாதையில் செல்வோம். தற்போதைய பாதை தீர்வுக்கு வழிவகுக்காது என்று ஒரு கட்டத்தில் நமக்குத் தெரிந்தால், நாங்கள் பின்வாங்கி அடுத்த தேர்வுக்கு செல்வோம்.

ஒவ்வொரு அடியிலும் பார்வையிட்டபடி தற்போதைய பாதையை எங்கள் பாதையில் குறிப்பதன் மூலம் கட்டத்தை சுற்றி வருவோம். ஒவ்வொரு அடியின் முடிவிலும் நாம் அதைக் குறிப்போம், இதன்மூலம் மற்றொரு திசையை முயற்சிக்க ஒரு சுத்தமான நிலை இருக்க வேண்டும்.

சொல் தேடல் லீட்கோட் தீர்வு

அல்காரிதம்

நாங்கள் ஒரு பின்வாங்கல் செயல்பாட்டைச் செய்வோம், இது ஒரு குறிப்பிட்ட கலத்துடன் தொடங்கி, டி.எஃப்.எஸ் பாணியில் கட்டத்தின் அருகிலுள்ள செல்களைக் கடந்து செல்லும். கொடுக்கப்பட்ட சொல் கட்டத்தில் எங்கிருந்தும் தொடங்கலாம் என்பதால், கட்டத்தின் அனைத்து கலங்களுக்கும் மேலாக நாம் வளைய வைப்போம், மேலும் ஒவ்வொரு கலத்திற்கும் இந்த தற்போதைய கலத்திலிருந்து தொடங்கி பின்வாங்கல் செயல்பாட்டை அழைப்போம்.
இந்த பின்னடைவு செயல்பாடு ஒரு சூத்திர செயல்பாடு, இந்த சுழல்நிலை செயல்பாட்டை செயல்படுத்துவதற்கான படிகள் கீழே உள்ளன:

  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 ஆக குறைக்கப்பட்டது. இந்த சுழல்நிலை செயல்பாட்டின் ஆழம் வார்த்தையின் நீளத்திற்கு (எல்) சமமாக இருக்கும். எனவே மோசமான நிலையில், செயல்பாட்டு அழைப்பின் மொத்த எண்ணிக்கை 3-நாரி மரத்தில் உள்ள முனைகளின் எண்ணிக்கையாக இருக்கும், இது சுமார் 3 ^ L ஆகும்.
மிக மோசமான நிலையில், இந்த செயல்பாட்டை N எண்ணிக்கையிலான கலங்களிலிருந்து தொடங்குகிறோம். எனவே ஒட்டுமொத்த நேர சிக்கலானது O (N * (3 ^ L)) ஆக இருக்கும்.

விண்வெளி சிக்கலானது 

ஓ (எல்): எல் என்பது கொடுக்கப்பட்ட வார்த்தையின் நீளம். இந்த இடம் மறுநிகழ்வு அடுக்குக்கு பயன்படுத்தப்படுகிறது.