share c++ dfs solution


  • 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++)
            {
                if (dfs(board, word, i, j, 0))
                    return true;
            }
        }
        return false;    
    }
    
    bool dfs(vector<vector<char>>& board, string word, int row, int col, int index)
    {
        if (index == word.size())
            return true;
        if (row < 0 || col < 0 || row >= board.size() || col >= board[0].size() || word[index] != board[row][col])
            return false;
        
        char tmp = board[row][col];
        board[row][col] = '0'; // board[row][col] is visited, next dfs visit board[row][col], word[index] must not equals '0'
        bool ret = dfs(board, word, row - 1, col, index + 1)
                || dfs(board, word, row + 1, col, index + 1)
                || dfs(board, word, row, col - 1, index + 1)
                || dfs(board, word, row, col + 1, index + 1);
        board[row][col] = tmp;
        
        return ret;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.