كلمة البحث  


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

البحث عن الكلمات يشبه ألغاز البحث عن الكلمات في وقت ما من حياتنا. اليوم أحمل على طاولة المفاوضات أ تم التعديل الكلمات المتقاطعة.

يجب أن يكون قرائي في حيرة من أمرهم حيال ما أتحدث عنه. دون إضاعة المزيد من الوقت ، دعونا نصل إلى بيان المشكلة

كلمة البحثدبوس
كلمات متقاطعة صغيرة على طول سطور البحث عن الكلمات.

هل يمكنك أن تجد كل الكلمات؟

يمكننا بناء الكلمة عموديًا أو أفقيًا المجاور الكلمات. الصيد هو أنه لا يمكنك استخدام نفس الحرف مرة أخرى.

مثال  

لنلقِ نظرة على بعض الأمثلة

الإدخال: [["A" ، "B" ، "C" ، "E"] ، ["S" ، "F" ، "C" ، "S"] ، ["A" ، "D" ، "E "،" E "]]

الكلمة: "ABCB"

الإخراج: صحيح

المدخلات [["A" ، "B" ، "C" ، "E"] ، ["S" ، "F" ، "C" ، "S"] ، ["A" ، "D" ، "E "،" E "]]

الكلمة: "انظر"

الإخراج: صحيح

ماذا نستطيع ان نفعل؟  

فيما يلي بعض النقاط التي نتبعها لإجراء بحث Word في اللغز.

  • مر عبر المصفوفة وابدأ من المكان الذي نجد فيه الحرف الأول
  • دع الحرف الحالي يكون cur وتحقق من السلسلة بشكل متكرر باستخدام DFS.
  • إذا وصلنا إلى نهاية الكلمة أي لدينا وجدت كل الشخصيات في المصفوفة نحن عودة صحيح
  • تحقق من كل حرف في المصفوفة
  • إذا كان الحرف موجودًا في الكلمة ، فابحث في الخلايا
    • أفقيا إلى الأمام
    • أفقيا وراء
    • عموديا أعلاه
    • عموديا أدناه
    • إذا كان هناك أي من المكالمات العودة صحيحة. ياي! لقد وجدنا الكلمة. نحن لسنا بحاجة للبحث بعد الآن
    • إرجاع 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)

أين،

م = طول المصفوفة

ن = عرض المصفوفة

l = طول الكلمة الواردة في مشكلة البحث عن الكلمات.

كيف؟

  • نجتاز اللوحة بأكملها في محاولة لمعرفة الحرف الأول من الكلمة المقدمة
    • في أسوأ الحالات ، قد نجتاز اللوحة بأكملها دون ضرب الحرف الأول
    • ثم نقوم بالبحث عن الشخصيات القريبة حتى نضغط على الحرف التالي
      • وهكذا نجتاز الكلمة بأكملها
      • التعقيد الزمني للقيام بذلك = O (L)
    • يمكن استدعاء هذه العملية O (L) في كل مرة في الحلقة الخارجية لـ O (M). جعل الوقت المعقد حتى الآن O (M * L)
  • العمليات المذكورة أعلاه تعمل في حلقة من O (N)
  • تتجمع الحلقات الثلاث معًا لجعل تعقيد الوقت = O (M * N * L)