leetcode练习 单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false

提示：

• m == board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board 和 word 仅由大小写英文字母组成

思路：本题可以利用回溯法，首先我们从board[0][0]开始，找到和word[0]相同的位置，进入回溯，从上下左右四个方向上找到未访问且和word匹配的位置，当index和word单词长度相同时，证明存在，flag置为true，在编写过程中，要注意边界位置和已访问位置的判断。我自己在编写代码时，有一个点困扰我较长时间，由于题目中给的word是string类型，而我想要用char数组来进行遍历，转化之后，因为在回溯时要判断index是否是等于word长度，因此要用strlen计算字符串长度，但我们要注意，如果在转化时，只将string成员转化过来，没有加'\0'就会发生越界报错。因此在编写时一定注意。

class Solution {
public:
    bool flag=false; 
    void backtracing(vector<vector<int>>&visited,char word[],vector<vector<char>>&board,int i,int j,int index)
    {
        if(flag)return ;
        int m=board.size();
        int n=board[0].size();
        
        if(index==strlen(word))
        {
            flag=true;
            return ;
        }
        if(i<0||i>=m||j<0||j>=n||board[i][j]!=word[index]||visited[i][j])
        {
            return ;
        }
        visited[i][j]=1;
        backtracing(visited,word,board,i-1,j,index+1);
        backtracing(visited,word,board,i+1,j,index+1);
        backtracing(visited,word,board,i,j-1,index+1);
        backtracing(visited,word,board,i,j+1,index+1);
        visited[i][j]=0;
    }
    bool exist(vector<vector<char>>& board, string word) {
        int m=board.size();
        int n=board[0].size();
        int len=word.size();
        char *arr=new char[len+1];
        for(int i=0;i<len;i++)
        {
            arr[i]=word[i];
        }
        arr[len]='\0';
        vector<vector<int>>visited(m,vector<int>(n,0));
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(board[i][j]==arr[0])
                {
                    backtracing(visited,arr,board,i,j,0);
                }
            }
        }
        return flag;
    }
};