වචන සෙවුම් ලීට්කෝඩ් විසඳුම


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ ඇමේසන් Apple ජංගම දුරකථන බ්ලූම්බර්ග් ByteDance සිස්කෝ ඊ බේ Expedia ෆේස්බුක් ඉන්ටයිට් මයික්රොසොෆ්ට් ඔරකල් Pinterest සර්විස්නව් 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

ප්‍රවේශය (පසුබැසීම)

මෙය ද්විමාන ජාලක ගමන් කිරීමේ ගැටළුවක් වන අතර, එහිදී ජාලකයේ යාබද සෛල භාවිතයෙන් දී ඇති වචනය සෑදිය හැකිදැයි පරීක්ෂා කිරීම සඳහා අපි ජාලකය ගවේෂණය කළ යුතුය. නමුත් සම්පූර්ණ ජාලක අවකාශයේ ඩීඑෆ්එස් සිදු කිරීම වෙනුවට අපි වඩාත් ප්‍රශස්ත ලෙස පසුගාමී ක්‍රමය භාවිතා කරමු. පසුගාමී ක්‍රමයේදී අපි එම මාර්ගයට යන්නේ අපගේ අරමුණට ගැලපෙන විසඳුම සෙවීම සඳහා පමණි. වර්තමාන මාවත විසඳුමට මඟ නොදෙන බව අපි යම් අවස්ථාවක දන්නේ නම්, අපි පසුපසට ගොස් ඊළඟ තේරීම සඳහා යමු.

සෑම පියවරකදීම සංචාරය කළ පරිදි අපගේ මාර්ගයේ වත්මන් කොටුව සලකුණු කිරීමෙන් අපි ජාලකය වටා ගමන් කරන්නෙමු. සෑම පියවරක් අවසානයේම අපි එය සලකුණු නොකරන්නෙමු, එවිට අපට වෙනත් දිශාවකට උත්සාහ කිරීමට පිරිසිදු තත්වයක් තිබිය හැකිය.

වචන සෙවුම් ලීට්කෝඩ් විසඳුම

ඇල්ගොරිතම

අපි පසුගාමී ක්‍රියාවලියක් සිදු කරනු ඇති අතර එය විශේෂිත සෛලයකින් ආරම්භ වන අතර යාබද ග්‍රිඩ් සෛල ඩීඑෆ්එස් විලාසිතාවෙන් ගමන් කරයි. දී ඇති වචනය විදුලිබල පද්ධතියේ ඕනෑම තැනක සිට ආරම්භ කළ හැකි බැවින්, අපි ජාලකයේ සියලුම සෛල හරහා ලූපයක් තබන අතර සෑම සෛලයකටම මෙම වත්මන් කොටුවෙන් ආරම්භ වන පසුබැසීමේ ශ්‍රිතය අමතන්නෙමු.
මෙම පසුගාමී ශ්‍රිතය a පුනරාවර්තන ශ්‍රිතය, මෙම පුනරාවර්තන ශ්‍රිතය ක්‍රියාත්මක කිරීමේ පියවර පහත දැක්වේ:

  1. ආරම්භයේ දී අපි පහළට හෝ පුනරාවර්තනයේ මූලික නඩුව වෙත ළඟා වී ඇත්දැයි පරීක්ෂා කරමු. සෙවිය යුතු වචනය හිස් නම් හෝ වෙනත් වචන වලින් එය සොයාගත හොත්, අපි සත්‍යය වෙත ආපසු යමු.
  2. අපි විදුලිබල පද්ධතියේ මායිම පසු කර ඇත්දැයි හෝ වත්මන් කොටුව සෙවුම් වචනයේ පළමු අක්‍ෂරයට ගැලපේද නැද්ද යන්න පරීක්ෂා කිරීමෙන් අපගේ මාර්ගය දැනට වලංගු ද නැද්ද යන්න අපි පරීක්ෂා කරමු.
  3. වත්මන් පියවර වලංගු නම්, මෙම කොටුව සංචාරය කළ ලෙස සලකුණු කරන්න. දකුණ, පහළ, වම සහ ඉහළ සෛල සඳහා එකම පසුගාමී ශ්‍රිතය ඇමතීමෙන් දිශාවන් හතර ගවේෂණය කිරීම ආරම්භ කරන්න.
  4. අවසානයේදී අපි වත්මන් කොටුවට පිවිස ගවේෂණයේ ප්‍රති result ල සත්‍ය හෝ අසත්‍ය ලෙස ලබා දෙමු. කිසියම් උප ගවේෂණයක් සත්‍ය නම්, අපි මෙතැන් සිට සත්‍යය වෙත ආපසු යමු.

ක්රියාත්මක කිරීම

වචන සෙවුම් ලීට්කෝඩ් විසඳුම සඳහා සී ++ වැඩසටහන

#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 දක්වා අඩු විය. මෙම පුනරාවර්තන ශ්‍රිතයේ මෙම ගැඹුර වචනයේ දිගට (L) සමාන වේ. එබැවින් නරකම අවස්ථාවක දී මුළු ක්‍රියාකාරී ආයාචනා ගණන 3-නාරි ගසෙහි ඇති නෝඩ් ගණන වන අතර එය 3 ^ L පමණ වේ.
නරකම අවස්ථාවක අපි මෙම ශ්‍රිතය හඳුන්වන්නේ සෛල N සංඛ්‍යාවෙන් ආරම්භ කරමිනි. එබැවින් සමස්ත කාල සංකීර්ණතාව O (N * (3 ^ L)) වේ.

අභ්‍යවකාශ සංකීර්ණතාව 

ඕ (එල්): මෙහි L යනු දී ඇති වචනයේ දිග වේ. මෙම අවකාශය පුනරාවර්තන සිරස් සඳහා භාවිතා වේ.