ដំណោះស្រាយពាក្យ Leetcode  


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ ក្រុមហ៊ុន Amazon ផ្លែប៉ោម ទីភ្នាក់ងារ Bloomberg ByteDance ស៊ីស្កូ របស់ eBay Expedia Facebook វិចារណញាណ ក្រុមហ៊ុន Microsoft ក្រុមហ៊ុន Oracle Pinterest ServiceNow ។ Snapchat
ក្បួនដោះស្រាយ បទថយក្រោយ ការសរសេរកូដ សំភាសន៍ កិច្ចសម្ភាសន៍ LeetCode LeetCodeSolutions ម៉ាទ្រីស

សេចក្តីថ្លែងការណ៍បញ្ហា។  

ដែលបានផ្តល់ឱ្យក្តារ 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

វិធីសាស្រ្ត (Backtracking)  

នេះគឺជាបញ្ហាឆ្លងកាត់ក្រឡាចត្រង្គ 2D ដែលយើងត្រូវស្វែងរកក្រឡាចត្រង្គដើម្បីពិនិត្យមើលថាតើពាក្យដែលបានផ្តល់អាចត្រូវបានបង្កើតឡើងដោយប្រើកោសិកាដែលនៅជាប់គ្នានៃក្រឡាចត្រង្គ។ ប៉ុន្តែជំនួសឱ្យការសម្តែង DFS នៅលើចន្លោះក្រឡាចត្រង្គទាំងមូលយើងនឹងប្រើវិធីសាស្រ្តនៃការនិយាយតបវិញកាន់តែប្រសើរ។ នៅក្នុងវិធីសាស្រ្តនៃការនិយាយថយក្រោយយើងនឹងទៅកាន់ផ្លូវនោះដើម្បីស្វែងរកដំណោះស្រាយដែលត្រូវនឹងគោលបំណងរបស់យើង។ ប្រសិនបើយើងដឹងនៅចំណុចខ្លះថាផ្លូវបច្ចុប្បន្ននឹងមិននាំទៅរកដំណោះស្រាយទេនោះយើងនឹងដើរថយក្រោយហើយទៅរកជម្រើសបន្ទាប់។

យើងនឹងឆ្លងកាត់ក្រឡាចត្រង្គដោយសម្គាល់ក្រឡាបច្ចុប្បន្ននៅក្នុងផ្លូវរបស់យើងដូចដែលបានទៅទស្សនានៅជំហាននីមួយៗ។ ហើយនៅចុងបញ្ចប់នៃជំហាននីមួយៗយើងក៏នឹងមិនគូសចំណាំវាដើម្បីឱ្យយើងមានស្ថានភាពស្អាតស្អំដើម្បីព្យាយាមទិសដៅផ្សេងទៀត។

ដំណោះស្រាយពាក្យ Leetcodeពិន

ក្បួនដោះស្រាយ  

យើងនឹងធ្វើឱ្យមុខងារដើរថយក្រោយដែលនឹងចាប់ផ្តើមជាមួយកោសិកាជាក់លាក់មួយហើយឆ្លងកាត់កោសិកាដែលនៅជាប់គ្នានៃក្រឡាចត្រង្គនៅក្នុងម៉ូដឌីអេសអេ។ ដោយសារតែពាក្យដែលបានផ្តល់អាចចាប់ផ្តើមពីគ្រប់ទិសទីនៃបណ្តាញអគ្គិសនីយើងនឹងបញ្ចោញកោសិកាទាំងអស់នៃក្រឡាចត្រង្គហើយសំរាប់កោសិកានីមួយៗយើងនឹងហៅមុខងារ backtracking ដែលចាប់ផ្តើមពីកោសិកាបច្ចុប្បន្ន។
ដូចមុខងារបញ្ច្រាស់បទនេះគឺក ហៅខ្លួនឯង មុខងារ, ខាងក្រោមនេះជាជំហានដើម្បីអនុវត្តមុខងារហៅនេះ:

  1. នៅដំណាក់កាលដំបូងយើងនឹងពិនិត្យមើលថាតើយើងបានទៅដល់បាតឬករណីមូលដ្ឋាននៃការហៅឡើងវិញ។ ប្រសិនបើពាក្យដែលត្រូវស្វែងរកគឺទទេឬនិយាយម្យ៉ាងទៀតប្រសិនបើវាត្រូវបានរកឃើញយើងត្រលប់មកវិញជាការពិត។
  2. យើងពិនិត្យមើលថាតើផ្លូវរបស់យើងបច្ចុប្បន្នមានសុពលភាពឬអត់ដោយពិនិត្យមើលថាតើយើងបានឆ្លងកាត់ព្រំដែននៃក្រឡាចត្រង្គឬប្រសិនបើក្រឡាបច្ចុប្បន្នត្រូវនឹងតួអក្សរដំបូងនៃពាក្យស្វែងរករឺអត់។
  3. ប្រសិនបើជំហានបច្ចុប្បន្នមានសុពលភាពបន្ទាប់មកសម្គាល់ក្រឡានេះដែលបានចូលមើល។ ហើយចាប់ផ្តើមស្វែងរកទិសដៅទាំងបួនដោយហៅមុខងារបទដដែលៗសម្រាប់កោសិកាខាងស្តាំចុះក្រោមឆ្វេងនិងឡើងលើ។
  4. នៅចុងបញ្ចប់យើងមិនបានទៅមើលកោសិកាបច្ចុប្បន្នហើយត្រឡប់លទ្ធផលនៃការរុករកថាជាការពិតរឺមិនពិត។ ប្រសិនបើលទ្ធផលនៃការរុករករងណាមួយជាការពិតយើងនឹងត្រឡប់ពីទីនេះវិញបើមិនដូច្នេះទេនឹងត្រឡប់មិនពិត។
សូម​មើល​ផង​ដែរ
ម៉ូរីសឆ្លងកាត់

ការអនុវត្តន៍  

កម្មវិធី 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

កម្មវិធីចាវ៉ាសំរាប់ដំណោះស្រាយពាក្យឡៃឡេកកូដ

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 ^ អិល))៖ ដែល N ជាចំនួនកោសិកាសរុបនៅក្នុងបណ្តាញអគ្គិសនីនិងអិលគឺជាប្រវែងនៃពាក្យដែលត្រូវស្វែងរក។ ចំពោះមុខងារនៃការនិយាយថយក្រោយដំបូងយើងទទួលបានជម្រើសចំនួន ៤ សម្រាប់ទិសដៅប៉ុន្តែវាបានបន្ថយមកត្រឹម ៣ ដូចដែលយើងបានទស្សនាវារួចហើយនៅក្នុងជំហានមុន។ ជម្រៅនៃមុខងារហៅឡើងវិញនេះនឹងស្មើនឹងប្រវែងនៃពាក្យ (អិល) ។ ដូច្នេះក្នុងករណីអាក្រក់បំផុតចំនួននៃការហៅរកមុខងារនឹងជាចំនួនថ្នាំងនៅក្នុងមែកធាង ៣ ណារីដែលមានប្រហែល ៣ ^ អិល។
ក្នុងករណីអាក្រក់បំផុតយើងហៅថាមុខងារនេះចាប់ផ្តើមពីលេខ N នៃកោសិកា។ ដូច្នេះភាពស្មុគស្មាញនៃពេលវេលាជារួមគឺ O (N * (3 ^ L)) ។

សូម​មើល​ផង​ដែរ
បញ្ចូលដំណោះស្រាយចន្លោះ Leetcode

ភាពស្មុគស្មាញនៃលំហ 

O (អិល)៖ ដែល L ជាប្រវែងនៃពាក្យដែលបានផ្តល់។ ចន្លោះនេះត្រូវបានប្រើសម្រាប់ជង់នៃការហៅខ្លួនឯង។

1