የቃል ፍለጋ Leetcode መፍትሔ


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን ፓም ብሉምበርግ ByteDance Cisco eBay Expedia ፌስቡክ ኢላማዊ የ Microsoft በ Oracle Pinterest አገልግሎቱ Snapchat
ወደ ኋላ መመለስ ማትሪክስ

የችግሩ መግለጫ

ለኤምኤክስኤን ቦርድ እና ቃል ከተሰጠ ቃሉ በፍርግርጉ ውስጥ ካለ ይፈልጉ ፡፡

ቃሉ የተገነባው በቅደም ተከተል በአጠገብ ካሉ ህዋሳት ፊደላት ሲሆን “በአጠገብ” ያሉት ህዋሳት በአግድም ሆነ በአቀባዊ ጎረቤት ከሆኑበት ነው ፡፡ ተመሳሳይ የፊደል ሕዋስ ከአንድ ጊዜ በላይ ጥቅም ላይ አይውልም ፡፡

ለምሳሌ

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)

ይህ የ 2 ዲ ፍርግርግ ተሻጋሪ ችግር ነው ፣ እኛ የተሰጠው ቃል በፍርግርጉ አጠገብ ያሉ ህዋሶችን በመጠቀም መፈጠር ይቻል እንደሆነ ለማጣራት ፍርግርግን መመርመር ያለብን ፡፡ ግን በፍርግርግ ቦታ ላይ DFS ን ከማከናወን ይልቅ በተሻለ ሁኔታ የመጠባበቂያ ዘዴን እንጠቀም ነበር። በኋላ ማፈግፈግ ዘዴ ከዓላማችን ጋር የሚስማማውን መፍትሄ ለማግኘት ወደዚያ መንገድ ብቻ እንሄዳለን ፡፡ የአሁኑ መንገድ ወደ መፍትሄ እንደማይወስድ በተወሰነ ደረጃ ካወቅን ወደኋላ እንመለሳለን እና ወደ ቀጣዩ ምርጫ እንሄዳለን ፡፡

በእያንዳንዱ ደረጃ እንደጎበኘን በመንገዳችን ውስጥ ያለውን የአሁኑን ሕዋስ ምልክት በማድረግ ወደ ፍርግርግ እንዞራለን ፡፡ እናም በእያንዳንዱ እርምጃ መጨረሻ እኛ ሌላ አቅጣጫ ለመሞከር ንፁህ ሁኔታ እንዲኖረን እንዲሁ ምልክት እናደርጋለን ፡፡

የቃል ፍለጋ Leetcode መፍትሔ

አልጎሪዝም

ከአንድ የተወሰነ ሕዋስ የሚጀምር እና በዲኤፍኤስኤስ ፋሽን ውስጥ የሚገኙትን የፍርግርግ ቅርበት ያላቸው ህዋሳትን የሚያቋርጥ የኋላ ማፈግፈግ ተግባር እንሰራ ነበር ፡፡ የተሰጠው ቃል በፍርግርጉ ውስጥ ከማንኛውም ቦታ ሊጀምር ስለሚችል ፣ እኛ በሁሉም የፍርግርጉ ህዋሶች ላይ እናልፋለን እናም ለእያንዳንዱ ሴል ከዚህ የአሁኑ ህዋስ ጀምሮ የኋላ ማፈግፈግ ተግባር እንለዋለን ፡፡
ይህ የኋላ ማፈግፈግ ተግባር ሀ ተደጋጋሚ ተግባር ከዚህ በታች የተደገመ ተግባርን ለመተግበር ደረጃዎች ከዚህ በታች ቀርበዋል

  1. በመነሻ ደረጃ ወደ ታችኛው ወይም ወደ ተሃድሶው መሰረታዊ ጉዳይ መድረሳችንን እንፈትሻለን ፡፡ የሚፈለግበት ቃል ባዶ ከሆነ ወይም በሌላ አነጋገር ከተገኘ ወደ እውነት እንመለሳለን ፡፡
  2. መንገዳችን በአሁኑ ጊዜ ትክክለኛ መሆኑን ወይም አለመሆኑን የምንመለከተው የፍርግርጉን ድንበር የተሻገርነው ስለመሆኑ ወይም የአሁኑ ሕዋስ ከፍለጋው ቃል የመጀመሪያ ባህሪ ጋር የሚዛመድ መሆኑን ወይም አለመሆኑን በማጣራት ነው ፡፡
  3. የአሁኑ እርምጃ ትክክለኛ ከሆነ ታዲያ ይህንን ሕዋስ እንደተጎበኙ ምልክት ያድርጉበት። እና ለቀኝ ፣ ለታች ፣ ለግራ እና ለላይ ህዋሶች ተመሳሳይ የመጠባበቂያ ተግባር በመደወል አራቱን አቅጣጫዎች መመርመር ይጀምሩ ፡፡
  4. በመጨረሻ የአሁኑን ሕዋስ ጎብኝተን የምርመራውን ውጤት እንደ እውነት ወይም ሐሰት እንመልሳለን ፡፡ የትኛውም ንዑስ ፍተሻ እውነት ከሆነ ውጤቱን ከዚያ ወደ እውነት እንመለሳለን አለበለዚያ ሐሰተኛ እንሆናለን ፡፡

አፈጻጸም

C ++ ፕሮግራም ለቃል ፍለጋ Leetcode Solution

#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

የጃቫ ፕሮግራም ለቃል ፍለጋ Leetcode Solution

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

ለቃል ፍለጋ Leetcode መፍትሄ ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (N * (3 ^ ሊ)): N በፍርግርጉ ውስጥ ያለው አጠቃላይ የሕዋሳት ብዛት እና L የሚፈለግበት የተሰጠው ቃል ርዝመት ነው። ለኋላ ማቋረጫ ተግባር በመጀመሪያ ለአቅጣጫዎች 4 ምርጫዎችን እናገኛለን ግን ከዚህ በፊት በነበረው ደረጃ ቀደም ብለን የጎበኘነው በመሆኑ ወደ 3 ቀንሷል ፡፡ ይህ የዚህ ተደጋጋሚ ተግባር ጥልቀት ከቃሉ (L) ርዝመት ጋር እኩል ይሆናል። ስለሆነም በጣም መጥፎ በሆነ ሁኔታ አጠቃላይ የሥራ ጥሪ ቁጥር በ 3 ናሪ ዛፍ ውስጥ የአንጓዎች ብዛት ይሆናል ፣ ይህም ወደ 3 ^ ኤል ነው ፡፡
በጣም በከፋ ሁኔታ ከኤን ቁጥር ሕዋሶች ጀምሮ ይህንን ተግባር እንጠራዋለን ፡፡ ስለዚህ አጠቃላይ የጊዜ ውስብስብነት O (N * (3 ^ ኤል)) ይሆናል።

የቦታ ውስብስብነት 

ኦ (ኤል) የተሰጠው ቃል ርዝመት የት ነው L. ይህ ቦታ ለሽርሽር ክምችት ጥቅም ላይ ይውላል ፡፡