C++刷题之旅（59）递归回溯

LeetCode算法入门（第五十九天） 递归 22.括号生成

class Solution {
public:
    void bracktracking(vector<string>& ans, string& cur, int left, int right, int n){
        if(cur.size() == n * 2){  //当括号总数量等于2倍的n时，才符合要求
            ans.push_back(cur);
            return;
        }
        if(left < n){   //左括号的数量不能超过n
            cur.push_back('(');
            bracktracking(ans, cur, left + 1, right, n);
            cur.pop_back();
        }
        if(right < left){   //右括号的数量不能超过左括号
            cur.push_back(')');
            bracktracking(ans, cur, left, right + 1, n);
            cur.pop_back();
        }
    }

    vector<string> generateParenthesis(int n) {
        vector<string> result;
        string current = "";
        bracktracking(result, current, 0, 0, n);
        return result;
    }
};

79.单词搜索

class Solution {
public:
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};   //方向数组

    bool dfs(vector<vector<char>>& board, string word, int x, int y, int index){
        if(board[x][y] != word[index]){
            return false;
        }
        if( index == word.size() - 1){
            return true;
        }
        char t = board[x][y];
        board[x][y] = '.';
        for(int i = 0; i < 4; i++){
            int xx = x + dx[i];
            int yy = y + dy[i];
            if(xx < 0 || xx >= board.size() || yy < 0 || yy >= board[0].size() || board[xx][yy] == '.'){   //越界或访问过
                continue;
            }
            if(dfs(board, word, xx, yy, index+1)){
                return true;
            }

        }
        board[x][y] = t;  //回溯
        return false;
    }

    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;
    }
};