โซลูชัน Leetcode ของ Word Search  


ระดับความยาก กลาง
ถามบ่อยใน อเมซอน แอปเปิล บลูมเบิร์ก ByteDance ซิสโก้ อีเบย์ Expedia Facebook ตรัสรู้ ไมโครซอฟท์ คำพยากรณ์ Pinterest ServiceNow Snapchat
อัลกอริทึม ย้อนรอย การเข้ารหัส สัมภาษณ์ สัมภาษณ์เตรียม LeetCode LeetCodeSolutions มดลูก

คำชี้แจงปัญหา  

รับบอร์ด mxn และคำค้นหาว่ามีคำนั้นอยู่ในตารางหรือไม่

คำนี้สามารถสร้างจากตัวอักษรของเซลล์ที่อยู่ติดกันตามลำดับโดยที่เซลล์ "ที่อยู่ติดกัน" จะอยู่ติดกันในแนวนอนหรือแนวตั้ง ห้ามใช้เซลล์ตัวอักษรเดียวกันมากกว่าหนึ่งครั้ง

ตัวอย่าง

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

word = "ABCCED"
true

คำอธิบาย:

โซลูชัน Leetcode ของ Word Search

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

word = "ABCB"
false

วิธีการ (การติดตามย้อนกลับ)  

นี่คือปัญหาการข้ามกริด 2 มิติที่เราต้องสำรวจตารางเพื่อตรวจสอบว่าคำที่กำหนดสามารถสร้างขึ้นโดยใช้เซลล์ที่อยู่ติดกันของกริดได้หรือไม่ แต่แทนที่จะแสดง DFS บนพื้นที่กริดทั้งหมดเราจะใช้วิธีการย้อนกลับอย่างเหมาะสมยิ่งขึ้น ในวิธีการย้อนกลับเราจะไปที่เส้นทางนั้นเพื่อค้นหาโซลูชันที่ตรงกับเป้าหมายของเราเท่านั้น หากเรารู้ในบางจุดว่าเส้นทางปัจจุบันจะไม่นำไปสู่การแก้ปัญหาเราจะย้อนกลับและเลือกตัวเลือกถัดไป

เราจะไปรอบ ๆ เส้นตารางโดยทำเครื่องหมายเซลล์ปัจจุบันในเส้นทางของเราว่าเยี่ยมชมในแต่ละขั้นตอน และในตอนท้ายของแต่ละขั้นตอนเราจะยกเลิกการทำเครื่องหมายเพื่อให้เรามีสถานะที่สะอาดเพื่อลองใช้ทิศทางอื่น

โซลูชัน Leetcode ของ Word Search

ขั้นตอนวิธี  

เราจะสร้างฟังก์ชัน backtracking ซึ่งจะเริ่มต้นด้วยเซลล์ใดเซลล์หนึ่งและสำรวจเซลล์ของกริดที่อยู่ติดกันในแบบ DFS เนื่องจากคำที่กำหนดสามารถเริ่มต้นจากที่ใดก็ได้ในตารางเราจะวนซ้ำเซลล์ทั้งหมดของตารางและสำหรับแต่ละเซลล์เราจะเรียกฟังก์ชันการย้อนกลับโดยเริ่มจากเซลล์ปัจจุบันนี้
เนื่องจากฟังก์ชันการย้อนรอยนี้เป็นไฟล์ ซ้ำ ฟังก์ชันด้านล่างนี้เป็นขั้นตอนในการใช้ฟังก์ชันเรียกซ้ำนี้:

  1. ในการเริ่มต้นเราจะตรวจสอบว่าเรามาถึงด้านล่างหรือกรณีฐานของการเรียกซ้ำหรือไม่ หากคำที่ต้องการค้นหาว่างเปล่าหรืออีกนัยหนึ่งหากพบเราจะคืนค่าจริง
  2. เราตรวจสอบว่าเส้นทางของเราถูกต้องหรือไม่โดยตรวจสอบว่าเราข้ามขอบเขตของเส้นตารางหรือไม่หรือเซลล์ปัจจุบันตรงกับอักขระตัวแรกของคำค้นหาหรือไม่
  3. หากขั้นตอนปัจจุบันถูกต้องให้ทำเครื่องหมายเซลล์นี้ว่าเยี่ยมชมแล้ว และเริ่มสำรวจทิศทางทั้งสี่โดยเรียกใช้ฟังก์ชันย้อนกลับเดียวกันสำหรับเซลล์ขวาลงซ้ายและขึ้น
  4. ในตอนท้ายเรายกเลิกการเยี่ยมชมเซลล์ปัจจุบันและส่งคืนผลลัพธ์ของการสำรวจว่าเป็นจริงหรือเท็จ หากการสำรวจย่อยใด ๆ ให้ผลลัพธ์เป็นจริงเราจะคืนค่าจริงจากที่นี่มิฉะนั้นจะคืนค่าเท็จ
ดูสิ่งนี้ด้วย
มอร์ริส Traversal

การดำเนินงาน  

โปรแกรม C ++ สำหรับ Word Search Leetcode Solution

#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 nary ซึ่งมีค่าประมาณ 3 ^ L
ในกรณีที่เลวร้ายที่สุดเราเรียกฟังก์ชันนี้โดยเริ่มจากจำนวนเซลล์ N ดังนั้นความซับซ้อนของเวลาโดยรวมจะเป็น O (N * (3 ^ L))

ดูสิ่งนี้ด้วย
แทรก Interval Leetcode Solution

ความซับซ้อนของอวกาศ 

O (L): โดยที่ L คือความยาวของคำที่กำหนด ช่องว่างนี้ใช้สำหรับการเรียกซ้ำสแต็ก