Word Search Leetcode шешімі  


Күрделілік дәрежесі орта
Жиі кіреді Amazon алма Bloomberg ByteDance Cisco еВау Expedia Facebook Intuit Microsoft Oracle Pinterest ServiceNow Snapchat
алгоритмдер Кері шегіну кодтау сұхбат сұхбат дайындау LeetCode LeetCodeSolutions Matrix

Проблемалық мәлімдеме  

Mxn тақтасы мен сөзін ескере отырып, сөздің торда бар-жоғын анықтаңыз.

Бұл сөзді «іргелес» ұяшықтар көлденең немесе тігінен көршілес орналасқан бірізді көрші ұяшықтардың әріптерінен құруға болады. Бір әріп ұяшығын бірнеше рет қолдануға болмайды.

мысал

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

word = "ABCCED"
true

Түсіндіру:

Word Search Leetcode шешімітүйреуіш

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

word = "ABCB"
false

Тәсіл (Backtracking)  

Бұл екі өлшемді торды кесіп өту проблемасы, мұнда берілген сөзді тордың іргелес ұяшықтары арқылы жасауға болатындығын тексеру үшін торды зерттеуге тура келеді. DFS-ті бүкіл тор кеңістігінде орындаудың орнына біз кері шегіну әдісін оңтайлы қолданар едік. Шегіну әдісі бойынша біз тек сол жолға біздің мақсатымызға сәйкес келетін шешімді табуға барамыз. Егер біз белгілі бір сәтте қазіргі жол шешімге апармайтынын білсек, онда біз кері шегініп, келесі таңдауға барамыз.

Біз әр қадамға барған жолдағы ағымдық ұяшықты белгілеу арқылы торды айналып өтеміз. Әр қадамның соңында біз басқа бағытты байқап көру үшін таза күйге ие болу үшін оны алып тастаймыз.

Word Search Leetcode шешімітүйреуіш

Алгоритм  

Біз белгілі бір ұяшықтан басталатын және DFS режимінде тордың іргелес ұяшықтарын айналып өтетін кері функцияларды орындайтын едік. Берілген сөз тордың кез келген жерінен басталуы мүмкін болғандықтан, біз тордың барлық ұяшықтарын айналып өтіп, әрбір ұяшық үшін осы ағымдағы ұяшықтан бастап кері трекинг функциясын шақырамыз.
Бұл функцияны а рекурсивті функциясы, төменде осы рекурсивті функцияны іске асырудың қадамдары келтірілген:

  1. Бастапқыда біз рекурсияның түбіне немесе негізгі жағдайға жеткен-жетпегенімізді тексереміз. Егер ізделетін сөз бос болса немесе басқаша табылған болса, біз шындыққа ораламыз.
  2. Біздің жолымыздың қазіргі уақытта дұрыс екендігін немесе жоқтығын біз тордың шекарасынан өткенімізді немесе ағымдағы ұяшық іздеу сөзінің бірінші таңбасына сәйкес келетіндігін немесе келмегендігін тексеру арқылы тексереміз.
  3. Егер ағымдағы қадам дұрыс болса, онда бұл ұяшықты барған ретінде белгілеңіз. Төрт бағытты зерттеуді оңға, төменге, солға және жоғары ұяшықтар үшін бірдей кері шақыру функциясын шақыру арқылы бастаңыз.
  4. Соңында біз ағымдағы ұяшыққа кірмей, зерттеу нәтижесін шын немесе жалған деп қайтарамыз. Егер барлаудың кез-келгені шындыққа тең болса, онда біз шындықты осыдан қайтарамыз, әйтпесе жалғанға қайтарамыз.
Сондай-ақ, қараңыз
Моррис Траверсал

Іске асыру  

Word Search Leetcode шешіміне арналған 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

Word Search Leetcode шешіміне арналған Java бағдарламасы

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

Word Search Leetcode шешімінің күрделілігін талдау  

Уақыттың күрделілігі

O (N * (3 ^ L)): Мұндағы N - тордағы ұяшықтардың жалпы саны, L - ізделетін берілген сөздің ұзындығы. Шегініс функциясы үшін бастапқыда біз бағыттар бойынша 4 таңдау аламыз, бірақ ол 3-ге дейін азайды, өйткені біз бұған алдыңғы қадамда барғанбыз. Бұл рекурсивті функцияның тереңдігі сөздің ұзындығына (L) тең болады. Демек, ең нашар жағдайда функцияны шақырудың жалпы саны 3-нар ағашындағы түйіндердің саны болады, ол шамамен 3 ^ L құрайды.
Нашар жағдайда біз бұл функцияны N ұяшықтар санынан бастаймыз. Демек, уақыттың жалпы күрделілігі O (N * (3 ^ L)) болады.

Сондай-ақ, қараңыз
Интерактивті шешім кодын енгізу

Ғарыштың күрделілігі 

O (L): мұндағы L - берілген сөздің ұзындығы. Бұл бос орын рекурсиялық стек үшін қолданылады.

1