Word Search Leetcode Solution  


مستوى الصعوبة متوسط
كثيرا ما يطلب في أمازون أجهزة آبل بلومبرغ ByteDance سيسكو يباي اكسبيديا فيس بوك يستشعر Microsoft أوراكل Pinterest الخدمة الآن Snapchat
خوارزميات التراجع الترميز المقابلة الشخصية مقابلة LeetCode LeetCodeSolutions مصفوفة

المشكلة بيان  

بالنظر إلى لوحة mxn وكلمة ، ابحث عما إذا كانت الكلمة موجودة في الشبكة.

يمكن إنشاء الكلمة من أحرف خلايا متجاورة بشكل تسلسلي ، حيث تكون الخلايا "المجاورة" متجاورة أفقيًا أو رأسيًا. لا يجوز استخدام نفس خلية الحرف أكثر من مرة.

مثال

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

word = "ABCCED"
true

التفسير:

Word Search Leetcode Solutionدبوس

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

word = "ABCB"
false

نهج (التراجع)  

هذه مشكلة اجتياز شبكة ثنائية الأبعاد ، حيث يتعين علينا استكشاف الشبكة للتحقق مما إذا كان يمكن تشكيل الكلمة المعطاة باستخدام الخلايا المجاورة للشبكة. ولكن بدلاً من أداء DFS على مساحة الشبكة بالكامل ، سنستخدم طريقة التراجع على النحو الأمثل. في طريقة التراجع ، سنذهب فقط إلى هذا المسار لإيجاد الحل الذي يتوافق مع هدفنا. إذا علمنا في مرحلة ما أن المسار الحالي لن يؤدي إلى الحل ، فسوف نتراجع ونذهب إلى الخيار التالي.

سنلتف حول الشبكة عن طريق وضع علامة على الخلية الحالية في مسارنا كما تمت زيارتها في كل خطوة. وفي نهاية كل خطوة ، سنقوم أيضًا بإلغاء تحديدها حتى نتمكن من الحصول على حالة نظيفة لمحاولة اتجاه آخر.

Word Search Leetcode Solutionدبوس

خوارزمية  

سنقوم بعمل وظيفة تراجع والتي ستبدأ بخلية معينة وتعبر الخلايا المجاورة للشبكة بأسلوب DFS. نظرًا لأن الكلمة المعطاة يمكن أن تبدأ من أي مكان في الشبكة ، فسنقوم بعمل حلقة فوق جميع خلايا الشبكة ولكل خلية سنقوم باستدعاء وظيفة التراجع بدءًا من هذه الخلية الحالية.
نظرًا لأن وظيفة التراجع هذه هي أ العودية دالة ، فيما يلي خطوات تنفيذ هذه الوظيفة العودية:

  1. في البداية سوف نتحقق مما إذا كنا قد وصلنا إلى الحالة السفلية أو الأساسية للتكرار. إذا كانت الكلمة المراد البحث عنها فارغة أو بعبارة أخرى إذا تم العثور عليها ، فإننا نرجع "صحيح".
  2. نتحقق مما إذا كان مسارنا صالحًا حاليًا أم لا عن طريق التحقق مما إذا كنا قد عبرنا حدود الشبكة أو إذا كانت الخلية الحالية تتطابق مع الحرف الأول من كلمة البحث أم لا.
  3. إذا كانت الخطوة الحالية صحيحة ، فقم بتمييز هذه الخلية على أنها تمت زيارتها. وابدأ في استكشاف الاتجاهات الأربعة عن طريق استدعاء وظيفة التراجع نفسها للخلايا اليمنى واليسرى واليسرى والعليا.
  4. في النهاية نقوم بإلغاء زيارة الخلية الحالية وإرجاع نتيجة الاستكشاف على أنها صحيحة أو خاطئة. إذا كان أي من الاستكشافات الفرعية صحيحة ، فإننا نعود صحيحًا من هنا وإلا نعيد القيمة false.
انظر أيضا
موريس ترافيرسال

تطبيق  

برنامج C ++ لحلول Leetcode البحث عن الكلمات

#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

برنامج Java لـ Word Search 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

تحليل التعقيد في Word Search Leetcode Solution  

تعقيد الوقت

O (N * (3 ^ L)): حيث N هو العدد الإجمالي للخلايا في الشبكة و L هو طول الكلمة المعطاة التي سيتم البحث عنها. بالنسبة لوظيفة التراجع في البداية ، نحصل على 4 خيارات للاتجاهات ولكن تم تقليلها إلى 3 كما قمنا بزيارتها بالفعل في الخطوة السابقة. سيكون عمق هذه الدالة العودية مساويًا لطول الكلمة (L). ومن ثم ، في أسوأ الحالات ، سيكون العدد الإجمالي لاستدعاء الوظيفة هو عدد العقد في شجرة ثلاثية ، وهو حوالي 3 ^ L.
في أسوأ الأحوال ، نسمي هذه الوظيفة بدءًا من عدد N من الخلايا. ومن ثم سيكون التعقيد الزمني الإجمالي O (N * (3 ^ L)).

انظر أيضا
أدخل حل Leetcode الفاصل

تعقيد الفضاء 

O (L): حيث L هو طول الكلمة المعطاة. يتم استخدام هذه المساحة لمكدس العودية.

1