শব্দ অনুসন্ধান লেটকোড সমাধান  


কাঠিন্য মাত্রা মধ্যম
প্রায়শই জিজ্ঞাসা করা হয় মর্দানী স্ত্রীলোক আপেল ব্লুমবার্গ ByteDance সিসকো ইবে এক্সপিডিয়া ফেসবুক যুক্তি তর্ক মাইক্রোসফট আকাশবাণী পিন্টারেস্ট ServiceNow Snapchat
আলগোরিদিম ব্যাকট্র্যাকিং আইনসংগ্রহ সাক্ষাত্কার সাক্ষাৎকারের প্রস্তুতি লেটকোড LeetCodeSolutions জরায়ু

সমস্যা বিবৃতি  

একটি এমএক্সএন বোর্ড এবং একটি শব্দ দেওয়া, গ্রিডে শব্দটি বিদ্যমান কিনা তা সন্ধান করুন।

শব্দটি অনুক্রমিকভাবে সংলগ্ন ঘরগুলির অক্ষর থেকে তৈরি করা যেতে পারে, যেখানে "সংলগ্ন" কোষগুলি অনুভূমিকভাবে বা উল্লম্বভাবে প্রতিবেশী are একই লেটার সেলটি একাধিকবার ব্যবহার করা যাবে না।

উদাহরণ

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

শব্দ অনুসন্ধান লিটকোড সমাধানের জন্য জটিলতা বিশ্লেষণ  

সময় জটিলতা

ও (এন * (3 ডিগ্রি এল)): যেখানে এন গ্রিডে মোট কক্ষের সংখ্যা এবং এল এটি দেওয়া শব্দের দৈর্ঘ্য। ব্যাকট্র্যাকিং ফাংশনটির জন্য প্রাথমিকভাবে আমরা দিকনির্দেশের জন্য 4 টি পছন্দ পাই তবে আরও এটি হ্রাস পেয়ে 3 হয়ে যায় কারণ আমরা ইতিমধ্যে এটি পূর্ববর্তী ধাপে পরিদর্শন করেছি। এই পুনরাবৃত্ত ফাংশনের এই গভীরতা শব্দের দৈর্ঘ্যের (এল) সমান হবে। অতএব সবচেয়ে খারাপ ক্ষেত্রে ফাংশন আহ্বানের মোট সংখ্যা 3-ন্যারি গাছের নোডের সংখ্যা হবে, যা প্রায় 3 ^ এল।
সবচেয়ে খারাপ ক্ষেত্রে আমরা এই ফাংশনটিকে কল করি N সংখ্যা থেকে শুরু করে। সুতরাং সামগ্রিক সময়ের জটিলতা ও (এন * (3 ^ এল)) হবে।

আরো দেখুন
অন্তর্বর্তী লেটকোড সমাধান sertোকান

স্পেস জটিলতা ity 

ও (এল): যেখানে এল প্রদত্ত শব্দের দৈর্ঘ্য। এই স্থানটি পুনরাবৃত্তি স্ট্যাকের জন্য ব্যবহৃত হয়।

1