სიტყვების ძებნა Leetcode Solution


Რთული ტური საშუალო
ხშირად ეკითხებიან Amazon Apple Bloomberg ByteDance Cisco eBay Expedia Facebook Intuit microsoft Oracle Pinterest სერვისი Snapchat
Backtracking Matrix

პრობლემის განცხადება

Mxn დაფისა და სიტყვის გათვალისწინებით, იპოვნეთ, თუ არსებობს სიტყვა ქსელში.

სიტყვა შეიძლება აგებულ იქნეს თანმიმდევრული მიმდებარე უჯრედების ასოებიდან, სადაც "მიმდებარე" უჯრედები ჰორიზონტალურად ან ვერტიკალურად მეზობლები არიან. ერთი და იგივე ასოს უჯრედის გამოყენება არ შეიძლება ერთზე მეტჯერ.

მაგალითი

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

word = "ABCCED"
true

განმარტება:

სიტყვების ძებნა Leetcode Solution

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

word = "ABCB"
false

მიდგომა (უკუჩვენება)

ეს არის 2D ქსელის გადაკვეთის პრობლემა, სადაც უნდა დავათვალიეროთ ქსელი, რათა შეამოწმოს შესაძლებელია მოცემული სიტყვის ფორმირება ქსელის მიმდებარე უჯრედების გამოყენებით. იმის ნაცვლად, რომ შევასრულოთ DFS ქსელის მთლიან სივრცეში, ჩვენ უფრო ოპტიმალურად გამოვიყენებთ უკუკავშირის მეთოდს. უკუქცევის მეთოდით, ჩვენ მხოლოდ იმ ბილიკზე მივდივართ, რათა ვიპოვოთ გამოსავალი, რომელიც შეესაბამება ჩვენს მიზანს. თუ გარკვეულ ეტაპზე ვიცით, რომ არსებული გზა არ გამოიწვევს გამოსავალს, ჩვენ უკან დავიბრუნებთ და მივყვებით შემდეგ არჩევანს.

ჩვენ შემოვივლით ბადეს, ჩვენს გზაზე არსებული უჯრედის აღნიშვნით, რომელიც თითოეულ ეტაპზე მოინახულა. ყოველი ნაბიჯის ბოლოს ჩვენ ასევე მოვახსენებთ მას, რომ გქონდეს სუფთა მდგომარეობა, რომ სხვა მიმართულება ვცადო.

სიტყვების ძებნა Leetcode Solution

ალგორითმი

ჩვენ შევადგენთ უკუქცევის ფუნქციას, რომელიც დაიწყება კონკრეტული უჯრით და გადავკვეთთ ქსელის მიმდებარე უჯრედებს DFS რეჟიმში. იმის გამო, რომ მოცემული სიტყვა შეიძლება დაიწყოს ბადის ნებისმიერი წერტილიდან, ჩვენ გადავხედავთ ბადის ყველა უჯრედს და თითოეული უჯრედისთვის მოვუწოდებთ უკუქცევის ფუნქციას ამ მიმდინარე უჯრიდან.
რადგან ეს უკუქცევის ფუნქცია არის რეკურსიული ქვემოთ მოცემულია ნაბიჯები ამ რეკურსიული ფუნქციის განსახორციელებლად:

  1. დასაწყისში შეამოწმებთ მივაღწიეთ თუ არა რეკურსის ქვედა ნაწილს ან ძირითად შემთხვევას. თუ საძიებო სიტყვა ცარიელია ან სხვა სიტყვებით რომ ვთქვათ, თუ იგი ნაპოვნია, ჩვენ ვუბრუნდებით ჭეშმარიტს.
  2. ჩვენ ვამოწმებთ, არის თუ არა ჩვენი გზა მოქმედი, თუ არა, გადავამოწმეთ, გადავკვეთეთ თუ არა ქსელის საზღვარი, ან ემთხვევა თუ არა მოქმედი უჯრედი საძიებო სიტყვის პირველ სიმბოლოს.
  3. თუ ამჟამინდელი ნაბიჯი მართებულია, მონიშნეთ ეს უჯრედი, როგორც ნამყოფი. და დაიწყეთ ოთხი მიმართულების შესწავლა მარჯვენა და ქვემო, მარცხენა და ზემოთ უჯრედების იგივე უკუქცევის ფუნქციის გამოძახებით.
  4. დასასრულს, ჩვენ ვეწვევით მიმდინარე უჯრედს და დავაბრუნებთ გამოკვლევის შედეგს, როგორც ჭეშმარიტს ან მცდარს. თუ რომელიმე ქვეკვლევის შედეგია ჭეშმარიტი, ჩვენ ვუბრუნდებით true- ს, თორემ false ვბრუნდებით.

განხორციელება

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 Solution- ისთვის

დროის სირთულე

O (N * (3 ^ L)): სადაც N არის ქსელში არსებული უჯრედების საერთო რაოდენობა, ხოლო L მოცემული სიტყვის სიგრძეა მოსაძიებელი. უკან დასაბრუნებელი ფუნქციისთვის თავდაპირველად ვიღებთ 4 არჩევანს მიმართულებებისთვის, მაგრამ შემდგომში ის შემცირდა 3 – მდე, რადგან მას უკვე ვესტუმრეთ წინა ეტაპზე. ამ რეკურსიული ფუნქციის ეს სიღრმე ტოლი იქნება სიტყვის სიგრძისა (L). ამიტომ, უარეს შემთხვევაში, ფუნქციის გამოძახების საერთო რაოდენობა იქნება 3-ნარიანი ხის კვანძების რაოდენობა, რაც დაახლოებით 3 ^ ლ.
უარეს შემთხვევაში ამ ფუნქციას ვუწოდებთ დაწყებული უჯრედების N რიცხვიდან. აქედან გამომდინარე, დროის საერთო სირთულე იქნება O (N * (3 ^ L)).

სივრცის სირთულე 

O (L): სადაც L მოცემული სიტყვის სიგრძეა. ეს სივრცე გამოიყენება რეკურსიული დასტისთვის.