වදන් සෙවුම  


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ ඇමේසන් Apple ජංගම දුරකථන බ්ලූම්බර්ග් ByteDance සිස්කෝ ෆේස්බුක් ඉන්ටයිට් මයික්රොසොෆ්ට් ඔරකල් සර්විස්නව් Snapchat
අරා පසුගාමී වීම

වචන සෙවීම යනු අපගේ ජීවිතයේ යම් කාලයකදී වචන සෙවීමේ ප්‍රහේලිකා වැනි ය. අද මම මේසය වෙත ගෙන එන්නේ අ වෙනස් කර ඇත හරස්පදය.

මා කතා කරන්නේ කුමක් ද යන්න පිළිබඳව මගේ පා ​​readers කයන් තරමක් ව්‍යාකූල විය යුතුය. තවත් කාලය නාස්ති නොකර ගැටළු ප්‍රකාශය වෙත යමු

වදන් සෙවුමපින්
සෙවුම් යන වචනයේ රේඛා ඔස්සේ කුඩා හරස්පදයක්.

ඔබට සියලු වචන සොයාගත හැකිද?

අපට වචනය සිරස් අතට හෝ තිරස් අතට සෑදිය හැකිය යාබද වචන. අල්ලන්න ඔබට නැවත එකම අකුර භාවිතා කළ නොහැක.

උදාහරණයක්  

උදාහරණ කිහිපයක් දෙස බලමු

ආදානය: [[““ ඒ ”,“ බී ”,“ සී ”,“ ඊ ”], [“ එස් ”,“ එෆ් ”,” සී ”,“ එස් ”], [“ ඒ ”,“ ඩී ”,” ඊ ”,” ඊ ”]]

වචනය: “ABCB”

ප්‍රතිදානය: ඇත්ත

ආදානය [[“A”, ”B”, “C”, “E”], [“S”, ”“ F ”,” C ”,” S ”], [“ A ”,“ D ”,” E ”,” ඊ ”]]

වචනය: “බලන්න”

ප්‍රතිදානය: ඇත්ත

අපිට මොනවද කරන්න පුළුවන්?  

ප්‍රහේලිකාව තුළ වචන සෙවීම සිදු කිරීම සඳහා අප අනුගමනය කරන කරුණු කිහිපයක් මෙන්න.

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

කේත ස්නිපටයක ආධාරයෙන් එය වඩා හොඳින් තේරුම් ගනිමු

වචන සෙවීම සඳහා ජාවා කේතය  

class Solution
{
    boolean trav(char[][] board,int cur,int i,int j,String word)
    {
       //If we have found all the characters
       if(cur>=word.length())
            return true;
       //In case the character does not match/we go out of the board
       if(i<0 || j<0 || i>=board.length || j>=board[i].length || 
          board[i][j]!=word.charAt(cur))
            return false;
        //Masking our board to prevent repetitive calls
        char temp=board[i][j];
        board[i][j]='*';
        boolean ans=(trav(board,cur+1,i+1,j,word) || trav(board,cur+1,i,j+1,word)
                     || trav(board,cur+1,i-1,j,word) || trav(board,cur+1,i,j-1,word));
        board[i][j]=temp;
            return ans;   
    }
    public boolean exist(char[][] board, String word) 
    {
        boolean ans=false;
        for(int i=0;i<board.length;i++)
        {
            for(int j=0;j<board[i].length;j++)
            {
                //We start checking from where we find the first character
                if(board[i][j]==word.charAt(0) && trav(board,0,i,j,word))
                {
                    return true;
                }
            }
        }
        return false;
    }
}

වචන සෙවීම සඳහා C ++ කේතය  

{
public:
    bool trav(vector<vector<char>>& board,int cur,int i,int j,string word)
    {
       if(cur>=word.length())
            return true;
       if(i<0 || j<0 || i>=board.size() || j>=board[i].size() || 
          board[i][j]!=word[cur])
            return false;
        char temp=board[i][j];
        board[i][j]='*';
        bool ans=(trav(board,cur+1,i+1,j,word) || trav(board,cur+1,i,j+1,word)
                     || trav(board,cur+1,i-1,j,word) || trav(board,cur+1,i,j-1,word));
        board[i][j]=temp;
            return ans;   
    }
public:
    bool exist(vector<vector<char>>& board, string word)
    {
     for(int i=0;i<board.size();i++)
     {
     for(int j=0;j<board[i].size();j++)
     {
     if(board[i][j]==word[0] && trav(board,0,i,j,word))
     {
     return true;
     }
     }
     }
    return false;   
    }
};
[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]

ABCB
true

සංකීර්ණ විශ්ලේෂණය  

කාල සංකීර්ණත්වය: O (m * n * l)

කොහේද,

m = අනුකෘතියේ දිග

n = අනුකෘතියේ පළල

l = වචන සෙවීමේ ගැටලුවෙහි දක්වා ඇති වචනයේ දිග.

කෙසේද?

  • සපයන ලද වචනයේ පළමු අකුර සොයා ගැනීමට අපි මුළු මණ්ඩලය හරහා ගමන් කරමු
    • නරකම අවස්ථාවෙහිදී, පළමු අක්ෂරයට පහර නොදී අපි මුළු පුවරුව හරහා ගමන් කළ හැකිය
    • ඊළඟ අක්ෂරයට පහර දෙන තෙක් අපි අසල ඇති අක්ෂර සොයන්නෙමු
      • මේ අනුව අපි මුළු වචනය හරහා ගමන් කරමු
      • එසේ කිරීමේ කාල සංකීර්ණතාව = O (L)
    • මෙම O (L) මෙහෙයුම O (M) හි පිටත පුඩුවේ සෑම අවස්ථාවකම ආයාචනය කළ හැකිය. O (M * L) දක්වා කාලය සංකීර්ණ කිරීම
  • ඉහත මෙහෙයුම් O (N) පුඩුවක් තුළ ක්‍රියාත්මක වේ
  • කාලය සංකීර්ණ වීම සඳහා ලූප තුන එකට එකතු වේ = O (M * N * L)