စကားလုံးရှာဖွေရေး Leetcode ဖြေရှင်းချက်  


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် အမေဇုံ Apple ဘလွန်းဘာ့ဂ် ByteDance Cisco သည် ကို eBay Expedia Facebook က အလိုလိုသိတတ်သော Microsoft က Oracle က Pinterest ServiceNow Snapchat
algorithms နောက်ပြန် coding အင်တာဗျူး အင်တာဗျူး LeetCode LeetCodeSolutions matrix

ပြProbleနာဖော်ပြချက်  

mxn ဘုတ်နှင့်စကားလုံးတစ်လုံးပေးထားသောစကားလုံးသည်ဇယားကွက်ထဲတွင်တည်ရှိမနေကိုရှာဖွေပါ။

အဆိုပါစကားလုံးကို "ကပ်လျက်" ဆဲလ်အလျားလိုက်သို့မဟုတ်ဒေါင်လိုက်အိမ်နီးချင်းရှိရာနောက်ဆက်တွဲကပ်လျက်ဆဲလ်၏အက္ခရာများ, ကနေတည်ဆောက်နိုင်ပါတယ်။ တူညီသောအက္ခရာဆဲလ်ကိုတစ်ကြိမ်ထက်ပိုပြီး အသုံးပြု၍ မရပါ။

နမူနာ

board = [["A","B","C","E"],
         ["S","F","C","S"],
         ["A","D","E","E"]],

word = "ABCCED"
true

ရှင်းလင်းချက်:

စကားလုံးရှာဖွေရေး Leetcode ဖြေရှင်းချက်တွယ်အပ်

board = [["A","B","C","E"],
         ["S","F","C","S"],
         ["A","D","E","E"]], 

word = "ABCB"
false

ချဉ်းကပ်မှု (နောက်ပြန်လှည့်ခြင်း)  

၎င်းသည် 2D ဇယားကွက်ဖြတ်သန်းခြင်းပြproblemနာဖြစ်သည်၊ ၎င်းသည်ဇယားကွက်၏ကပ်လျက်ဆဲလ်များကို အသုံးပြု၍ ပေးထားသောစကားလုံးဟုတ်မဟုတ်စစ်ဆေးရန်ဇယားကွက်ကိုလေ့လာရန်ဖြစ်သည်။ ဒါပေမယ့် DFS ကို grid space တစ်ခုလုံးမှာလုပ်မယ့်အစား backtracking နည်းလမ်းကိုပိုပြီးကောင်းအောင်လုပ်မယ်။ backtracking နည်းစနစ်တွင်ကျွန်ုပ်တို့၏ရည်မှန်းချက်နှင့်ကိုက်ညီသောအဖြေကိုသာရှာဖွေရန်လမ်းကြောင်းသို့သွားလိမ့်မည်။ အကယ်၍ ကျွန်ုပ်တို့လက်ရှိလမ်းကြောင်းသည်ဖြေရှင်းချက်ဆီသို့ ဦး တည်သွားလိမ့်မည်မဟုတ်ကြောင်းတစ်ချိန်ချိန်သိလျှင်ကျွန်ုပ်တို့သည်နောက်သို့လှည့်ကာနောက်လာမည့်ရွေးချယ်မှုကိုသွားလိမ့်မည်။

အဆင့်တစ်ခုစီသို့လည်ပတ်နေသည့်အတိုင်းကျွန်ုပ်တို့၏လမ်းကြောင်းရှိလက်ရှိဆဲလ်ကိုအမှတ်အသားပြုခြင်းဖြင့်ဇယားကွက်ကိုလှည့်ပတ်သွားပါမည်။ နောက်အဆင့်တစ်ခုချင်းစီကိုအဆုံးသတ်ဖို့အတွက်သန့်ရှင်းတဲ့အနေအထားရှိအောင်အဆင့်တစ်ခုချင်းစီရဲ့အဆုံးသတ်ကိုမှတ်သားပါမယ်။

စကားလုံးရှာဖွေရေး Leetcode ဖြေရှင်းချက်တွယ်အပ်

algorithm  

ကျွန်ုပ်တို့သည်ဆဲလ်တစ်ခုနှင့် စတင်၍ DFS ဖက်ရှင်ဇယားကွက်ရှိဆဲလ်များကိုဖြတ်သန်းသွားမည့် backtracking function ကိုလုပ်လိမ့်မည်။ ပေးထားသောစကားလုံးသည်ဇယားကွက်ရှိမည်သည့်နေရာမှမဆိုစတင်နိုင်သောကြောင့်၊ ကျွန်ုပ်တို့သည်ဇယားကွက်ရှိဆဲလ်များအားလုံးကိုကွင်းဆက် လိုက်၍ ဆဲလ်တစ်ခုချင်းစီအတွက်လက်ရှိဆဲလ်မှစတင်သော backtracking function ကိုခေါ်လိမ့်မည်။
ဒီ backtracking function ကိုအဖြစ် ကုထုံး function ကိုအောက်တွင်ဖော်ပြထားသည်မှာဤ recursive function ကိုအကောင်အထည်ဖော်ရန်ဖြစ်သည်။

  1. အစအ ဦး ၌ကျွန်ုပ်တို့သည်အောက်ခြေသို့ရောက်ခဲ့ခြင်းရှိမရှိသို့မဟုတ်ပြန်လည်လေ့လာခြင်း၏အခြေခံအမှုကိစ္စကိုစစ်ဆေးပါမည်။ ရှာဖွေရမည့်စကားလုံးသည်အချည်းနှီးသို့မဟုတ်တစ်နည်းအားဖြင့်၎င်းကိုတွေ့ရှိပါကကျွန်ုပ်တို့သည်စစ်မှန်ကြောင်းပြန်လာကြမည်။
  2. ကျွန်ုပ်တို့၏လမ်းကြောင်းသည်လတ်တလောမှန်ကန်မှုရှိမရှိစစ်ဆေးသည်သို့မဟုတ်ကျွန်ုပ်တို့သည်ဇယားကွက်၏နယ်နိမိတ်ကိုကျော်ဖြတ်ပြီးပြီလားသို့မဟုတ်လက်ရှိဆဲလ်သည်ရှာဖွေရေးစကားလုံး၏ပထမအက္ခရာနှင့်ကိုက်ညီမှုရှိမရှိစစ်ဆေးသည်။
  3. အကယ်၍ လက်ရှိအဆင့်သည်မှန်ကန်လျှင်၊ ဤဆဲလ်ကိုလာရောက်လည်ပတ်သူအဖြစ်မှတ်သားပါ။ ပြီးတော့ညာဘက်၊ အောက်၊ ဘယ်ဖက်နဲ့အထက်ဆဲလ်တွေအတွက်တူညီတဲ့ backtracking function ကိုခေါ်ယူခြင်းဖြင့်လမ်းညွှန်လေးခုကိုစလေ့လာပါ။
  4. အဆုံးမှာလက်ရှိဆဲလ်ကိုမသွားတော့ဘဲရှာဖွေတူးဖော်မှု၏ရလဒ်ကိုမှန်လားမှားလားသို့ပြန်ပို့သည်။ အကယ်၍ ရှာဖွေတွေ့ရှိမှုမှရလဒ်တစ်ခုခုသည်မှန်ကန်ပါကကျွန်ုပ်တို့မှဤနေရာမှအမှန်ပြန်လာပါကမဟုတ်ပါ။
လည်းကြည့်ရှုပါ
မောရစ် Traversal

အကောင်အထည်ဖော်ရေး  

Word Search Leetcode Solution အတွက် C ++ အစီအစဉ်

#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

Word Search Leetcode Solution အတွက် Java အစီအစဉ်

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

Word Search Leetcode Solution အတွက်ရှုပ်ထွေးမှုဆန်းစစ်ခြင်း  

အချိန်ရှုပ်ထွေး

အို (N * (၃ ^ L)) N သည်ဇယားကွက်ရှိဆဲလ်အရေအတွက်နှင့် L သည်ရှာဖွေရမည့်စကားလုံး၏အရှည်ဖြစ်သည်။ backtracking လုပ်ဆောင်မှုအတွက်ကန ဦး လမ်းညွှန်များအတွက်ရွေးချယ်မှု ၄ ခုရခဲ့သော်လည်းယခင်အဆင့်သို့သွားပြီးဖြစ်သောကြောင့်၎င်းသည် ၃ သို့လျှော့ချခဲ့သည်။ ဒီ recursive function ရဲ့အတိမ်အနက်ဟာစကားလုံး (L) ရဲ့အရှည်နဲ့ညီမျှလိမ့်မယ်။ ထို့ကြောင့်အဆိုးဆုံးကိစ္စတွင် function invocation စုစုပေါင်းသည် 4 ^ L ဖြစ်သော 3-nary tree ရှိ node များအရေအတွက်ဖြစ်သည်။
အဆိုးဆုံးကိစ္စကတော့ဒီ function ကိုဆဲလ်နံပါတ် N ကနေစတယ်။ ထို့ကြောင့်အချိန်ရှုပ်ထွေးမှုသည်အို (N * (3 ^ L)) ဖြစ်လိမ့်မည်။

လည်းကြည့်ရှုပါ
Interval Leetcode ဖြေရှင်းချက်ထည့်ပါ

အာကာသရှုပ်ထွေးမှု 

အို (လ) L သည်ပေးထားသောစကားလုံး၏အရှည်ဖြစ်သည်။ ဒီအာကာသကို recursion stack အတွက်အသုံးပြုသည်။

1