[beginners climb Leetcode79] Word Search

Leetcode79 medium\color{#FF4500}{medium}medium
Click to enter the original question link: Word Search
Related topics: word search II word search II
[tag] backtracking search, C++ ASCII

subject

Discription

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

Problem solving

A conventional backtracking algorithm, in the process of recursion, carries out DFS search in four directions. The code is as follows:

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        if(board.empty()||board[0].empty()) return false;  //Empty case
        int m = board.size(); 
        int n = board[0].size();
        int dx[] = {0,1,0,-1}; //x coordinate changes in four directions
        int dy[] = {1,0,-1,0}; //y coordinate changes in four directions
        for(int y = 0;y<m;y++){
            for(int x = 0;x<n;x++){
                if(DFS(board,word,0,x,y,dx,dy,m,n)) return true; //If you find a path that matches, you can directly return true
            }
        }
        return false;
    }
private:
    bool DFS(vector<vector<char>>& board, const string& word,int word_index,int x,int y,const int* dx,const int* dy,const int& m,const int& n){
        if(word[word_index]!=board[y][x]) return false;
        board[y][x] += 128; //Adding 128 directly to char is equivalent to adding a lock to prevent repeated traversal
        if(word_index==word.size()-1) return true;
        for(int i=0;i<4;i++){
            int new_x = x+dx[i];
            int new_y = y+dy[i];
            if(new_x>=0 && new_x<n && new_y>=0 && new_y<m ){
                if(DFS(board,word,word_index+1,new_x,new_y,dx,dy,m,n)) return true;
            }
        }
        board[y][x] -= 128; //Unlock
        return false;
    }
};

Here are several points worth noting:

  1. At the beginning of the recursive function, judge whether the current letter is what we are looking for (that is, whether the search direction is correct), which can save the code of finding the starting point of the search. It can not only find the starting point of search, but also judge the search direction.
 bool DFS(vector<vector<char>>& board, const string& word,int word_index,int x,int y,const int* dx,const int* dy,const int& m,const int& n){
        if(word[word_index]!=board[y][x]) return false;
  1. Instead of using an additional visited array to avoid going back, we directly modify the elements of the original board array:
board[y][x] += 128; //Adding 128 directly to char is equivalent to adding a lock to prevent repeated traversal
...
board[y][x] -= 128; //Unlock

The specific value of ASCII code can be Look here , C + + takes the remainder 256 directly for ASCII code overflow (more than 256), and adds or subtracts 256 for a char type, which is equal to no change, so 128 is used here.

  1. When we find the last char, the direct stop function returns true, but the position of board[y][x] is not unlocked at this time, that is, board[y][x] -= 128. There is no effect in this problem, because it will end as long as the last char is found, but when word search II wants to search a pile of words, it needs to be careful not to affect the search of other words.
if(word_index==word.size()-1) return true;

Tags: C++ Algorithm data structure leetcode

Posted by snaack on Tue, 24 May 2022 01:57:25 +0300