詞搜索


難度級別
經常問 亞馬遜 蘋果 彭博社 ByteDance 思科 Facebook 意會 Microsoft微軟 神諭 的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”]]

字詞:“ SEE”

輸出:真

我們可以做什麼?

以下是我們在拼圖中執行單詞搜索所遵循的一些要點。

  • 遍歷矩陣並從找到第一個字母的地方開始
  • 讓當前字符為cur並使用遞歸檢查字符串 DFS。
  • 如果我們到達單詞的末尾,即我們有 找到所有的人物 在矩陣中 返回true
  • 檢查矩陣的每個字符
  • 如果字符在單詞中,請查看單元格
    • 水平前方
    • 水平向後
    • 垂直上方
    • 垂直下方
    • 如果有電話 返回true。 耶! 我們找到了這個詞。 我們不再需要搜索
    • 從所有通話中返回“或”
  • 如果找不到該字符,我們返回 假 
  • 為確保我們不返回到同一單元格,我們使用一個流浪漢字掩蓋每個單元格的值

讓我們藉助代碼片段更好地理解它

用於單詞搜索的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(M)的外循環中調用此O(L)操作。 到目前為止,使時間變得複雜O(M * L)
  • 以上操作以O(N)循環運行
  • 三個循環合在一起使時間複雜度= O(M * N * L)