8.8 dfs

to do

Paste_Image.png

10.9] Generate Parentheses

path如果是string而不是vector，为了写简的话直接pass by val就不push pop by ref了
主要是想到有哪些possible try，什么条件下。一开始在想dp？

    void dfs(vector<string>& ret, string path, int leftCt, int rightCt, int n) {
        if (rightCt==n) {
            ret.push_back(path);
            return;
        } 
        if (leftCt<n) 
            dfs(ret, path+"(", leftCt+1, rightCt, n);
        if (rightCt<leftCt) 
            dfs(ret, path+")", leftCt, rightCt+1, n);
    }
    
    vector<string> generateParenthesis(int n) {
        vector<string> ret;
        dfs(ret, "", 0, 0, n);
        return ret;
    }

btw] Valid Sudoku

note the way to map board[i][j] to some 3*3 box, determins its row (0-2) then *3 to get the index of the starting elem at the row, +col to be at the exact index.

    bool isValidSudoku(vector<vector<char>>& board) {
        // row i * col j
        // e.g. checkRow[i][num] num occurred at row i?
        int checkRow[9][9] = {0}, checkCol[9][9] = {0}, checkBox[9][9] = {0};
        for (int i=0; i<board.size(); ++i) {
            for (int j=0; j<board[0].size(); ++j) {
                if (board[i][j] == '.') continue;
                int num = board[i][j]-'0'-1; // suduku has 1-9
                if (checkRow[i][num] || checkCol[j][num] || checkBox[i / 3 * 3 + j / 3][num]) return false;
                checkRow[i][num] = checkCol[j][num] = checkBox[i / 3 * 3 + j / 3][num] = 1;
            }
        }
        return true;
    }

10.10] Sudoku Solver

note where to trim, stuck in loop before.
Also did char < '10' .. :(
And initially didn't want to search again from [0, 0] every time. However, it gets tricky to make sure always searching the next box. (If really want to, try keeping track of one overall index)

    bool okToPlace(vector<vector<char>>& board, char c, int row, int col) {
        int boxi = row/3*3, boxj = col/3*3;
        for (int i=0; i<9 ; ++i) {
            if (board[i][col] == c || board[row][i] == c) return false;
        }
        for (int i=boxi; i<boxi+3; ++i) {
            for (int j=boxj; j<boxj+3; ++j) {
                if (board[i][j] == c) return false;
            }
        }
        return true;
    }

    bool dfs(vector<vector<char>>& board) {
        for (int i=0; i<9; ++i) {
            for (int j=0; j<9; ++j) {
                if (board[i][j]!='.') continue;
                for (char c='1'; c<='9'; ++c) {
                    if (okToPlace(board, c, i, j)) {
                        board[i][j] = c;
                        if (dfs(board)) return true;
                        board[i][j] = '.';
                    }
                }
                return false; // important, no move possible here to make it work 
            }
        }
        return true;
    }
    
    void solveSudoku(vector<vector<char>>& board) {
        dfs(board);
    }

10.11] Word Search

note how it uses var solvable to avoid duplicate try push and pop.

    bool okToUse(vector<vector<char>>& board, vector<vector<bool>>& used, int i, int j, char charToUse) {
        if (i<0 || i>=board.size() || j<0 || j>=board[0].size()) return false;
        return charToUse == board[i][j] && !used[i][j];
    }
    
    bool dfs(vector<vector<char>>& board, vector<vector<bool>>& used, string& word, int level, int i, int j) {
        if (level == word.size()) return true;
        bool solvable = false;
        if (okToUse(board, used, i, j, word[level])) {
            used[i][j] = true;
            solvable = dfs(board, used, word, level+1, i+1, j) ||
                       dfs(board, used, word, level+1, i, j+1) ||
                       dfs(board, used, word, level+1, i-1, j) ||
                       dfs(board, used, word, level+1, i, j-1);
           used[i][j] = false;
        }
        return solvable;
    }
    
    bool exist(vector<vector<char>>& board, string word) {
        vector<vector<bool>> used (board.size(), vector<bool> (board[0].size(), false));
        for (int i=0; i<board.size(); ++i) {
            for (int j=0; j<board[0].size(); ++j) {
                 if (dfs(board, used, word, 0, i, j))
                    return true;
            }
        }
        return false;
    }