LeetCode#79

LeetCode#79单词搜索

题目链接
一道看似简单深搜回溯,需要注意在回溯过程中判断结束回溯的条件(图的边界,字符串长度)

class Solution {
public:
    int flag[205][205];
    bool ans = false;
    void dfs(vector<vector<char>>& board,int x,int y,string& word,int pos)
    {   
        //cout << x << y << word << pos << endl;
        if(x < 0 
        || x >= board.size() 
        || y < 0 
        || y >= board[0].size() 
        || board[x][y] != word[pos] 
        || flag[x][y] ==1
        || ans == true)
            return;
        //cout << board[x][y] << " " << x << " " << y  << " "  << pos << endl;
        if(flag[x][y] == 0)
        {
            if(pos == word.size() - 1)
            {
                ans = true;
                return;
            }
            flag[x][y] = 1;
            dfs(board,x+1,y,word,pos+1);
            dfs(board,x-1,y,word,pos+1);
            dfs(board,x,y+1,word,pos+1);
            dfs(board,x,y-1,word,pos+1);
            flag[x][y] = 0;
        }
    }
    bool exist(vector<vector<char>>& board, string word) {
        for(int i = 0 ; i < board.size() ; i++)
            for(int j = 0; j < board[0].size() ; j++)
                dfs(board,i,j,word,0);
        return ans;
    }
};

传递形参时,会在栈内重新构建数组,传引用则不会(或使用全局数组),二者在空间和时间复杂度上都差很多