חיפוש מילה


רמת קושי בינוני
נשאל לעתים קרובות אמזון בעברית תפוח עץ בלומברג Byte סיסקו פייסבוק אינטואיט מיקרוסופט אורקל ServiceNow 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 ”]]

מילה: "ראה"

פלט: נכון

מה אנחנו יכולים לעשות?

להלן מספר נקודות שאנו עוקבים אחר ביצוע חיפוש מילים בפאזל.

  • דלג על המטריצה ​​והתחל מהמקום בו אנו מוצאים את האות הראשונה
  • תנו לדמות הנוכחית להיות מרוסנת ובדקו באמצעות המחרוזת באופן רקורסיבי DFS.
  • אם נגיע לסוף המילה כלומר יש לנו מצא את כל הדמויות במטריקס אנחנו לחזור אמית
  • בדוק כל תו של המטריצה
  • אם הדמות נמצאת במילה הביטו בתאים
    • אופקית קדימה
    • אופקית מאחור
    • אנכית מעל
    • אנכית למטה
    • אם אחת מהשיחות לחזור אמיתי. יש! מצאנו את המילה. אנחנו לא צריכים לחפש יותר
    • החזר OR מכל השיחות
  • אם הדמות לא נמצאת אנו חוזרים שקר 
  • כדי להבטיח שלא נמשיך לחזור לאותו תא אנו מסווים את הערך של כל תא עם תו תועה

תן לנו להבין את זה טוב יותר בעזרת קטע קוד

קוד Java לחיפוש מילים

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)

איפה,

m = אורך המטריצה

n = רוחב המטריצה

l = אורך המילה הנתון בבעיית חיפוש המילים.

איך?

  • אנו עוברים את הלוח כולו ומנסים לברר את האות הראשונה של המילה שסופקה
    • במקרה הגרוע ביותר, אנו עשויים לחצות את הלוח כולו מבלי להכות את הדמות הראשונה
    • לאחר מכן אנו מחפשים את הדמויות הסמוכות עד שנלחץ על הדמות הבאה
      • כך אנו עוברים את המילה כולה
      • מורכבות הזמן בכך = O (L)
    • ניתן להפעיל פעולת O (L) בכל פעם בלולאה החיצונית של O (M). ביצוע מורכבות זמן עד עכשיו O (M * L)
  • הפעולות הנ"ל פועלות בלולאה של O (N)
  • שלושת הלולאות מתאחדות כדי להפוך את מורכבות הזמן = O (M * N * L)