LeetCode.17.22.79(递归&回溯)

17.电话号码的字母组合

class Solution {
  public:
    vector<string> ans;
    vector<string> dictionary = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    string path;
    vector<string> letterCombinations(string digits) {
        if (digits.empty())
            return {};
        find(digits, 0);
        return ans;
    }
    void find(string digits, int pos) {
        if (pos == digits.size()) {
            ans.push_back(path);
            return;
        }
        for (int i = 0; i < dictionary[digits[pos] - '2'].size(); i++) {
            path.push_back(dictionary[digits[pos] - '2'][i]);
            find(digits, pos + 1);
            path.pop_back();
        }
    }
    // 25/25 cases passed (0 ms)
    // Your runtime beats 100 % of cpp submissions
    // Your memory usage beats 89.75 % of cpp submissions (6.3 MB)
};

22.括号生成

class Solution {
  public:
    vector<string> ans;
    string path;
    vector<string> generateParenthesis(int n) {
        produce(n, n);
        return ans;
    }
    void produce(int left, int right) {
        if (right < left)
            return;
        if (left == 0 && right == 0) {
            ans.push_back(path);
            return;
        }
        if (left > 0) {
            path.push_back('(');
            produce(left - 1, right);
            path.pop_back();
        }
        if (right > 0) {
            path.push_back(')');
            produce(left, right - 1);
            path.pop_back();
        }
    }
    // 8/8 cases passed (0 ms)
    // Your runtime beats 100 % of cpp submissions
    // Your memory usage beats 64.58 % of cpp submissions (11.2 MB)
};

79.单词搜索

class Solution {
  public:
    /* int dirX[4] = {0, 1, 0, -1};
    int dirY[4] = {1, 0, -1, 0};
    string path;
    bool exist(vector<vector<char>> &board, string word) {
        vector<int> hash1(128, 0);
        for (auto &&i : board) {
            for (auto &&j : i) {
                hash1[j]++;
            }
        }
        vector<int> hash2(128, 0);
        for (auto &&i : word) {
            hash2[i]++;
        }
        for (int i = 0; i < 128; i++)
            if (hash1[i] < hash2[i])
                return 0;
        for (int i = 0; i < board.size(); i++)
            for (int j = 0; j < board[0].size(); j++) {
                if (board[i][j] == word[0])
                    if (find(board, word, j, i, 0))
                        return 1;
            }
        return 0;
    }
    bool find(vector<vector<char>> board, string word, int x, int y, int pos) {
        if (pos >= word.size())
            return 1;
        if (x < 0 || x > board[0].size() - 1 || y < 0 || y > board.size() - 1 || board[y][x] != word[pos])
            return 0;
        bool ans = 0;
        char temp = board[y][x];
        board[y][x] = ' ';
        for (int i = 0; i < 4; i++) {
            path.push_back(temp);
            ans = ans || find(board, word, x + dirX[i], y + dirY[i], pos + 1);
            path.pop_back();
        }
        return ans;
    }
    //超时 */
    int dirX[4] = {0, 1, 0, -1};
    int dirY[4] = {1, 0, -1, 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 (board[i][j] == word[0])
                    if (find(board, word, j, i, 0))
                        return 1;
            }
        return 0;
    }
    bool find(vector<vector<char>> &board, string &word, int x, int y, int pos) {
        if (pos >= word.size())
            return 1;
        if (x < 0 || x > board[0].size() - 1 || y < 0 || y > board.size() - 1 || board[y][x] != word[pos])
            return 0;
        bool ans = 0;
        board[y][x] += 128;
        for (int i = 0; i < 4; i++) {
            ans = ans || find(board, word, x + dirX[i], y + dirY[i], pos + 1);
        }
        board[y][x] -= 128;
        return ans;
    }
    /*
    //find的word前没有&
    // 83/83 cases passed (640 ms)
    // Your runtime beats 24.1 % of cpp submissions
    // Your memory usage beats 85.68 % of cpp submissions (7.7 MB)
    */
    /*
    //find的word前有&
    // 83/83 cases passed (204 ms)
    // Your runtime beats 85.28 % of cpp submissions
    // Your memory usage beats 91.03 % of cpp submissions (7.6 MB)
    */
    //*加了&变成引用形参
    /* 用引用肯定可以提高效率，不过要看情况，只有当引用的是占用“较大的内存空间的对象或结构体变量”时，才可能节约更多的时间。简单变量的引用不会节省空间。道理是这样的：
    当实参是较大的对象或结构体变量时，如果直接传递给相应的函数形参，需要创建临时对象或结构本变量，而且还需要复制大块内存数据，这肯家比只传递一个“引用”（实际上是一种变形指针）要耗时得多。
    如果你想测试的话，你应该构造“大点”的对象或结构体变量才行。
    */
    //原因是少了个创建、复制的步骤？
    // "AAAAAAAAAAAAABB"
    // [["A","A","A","A","A","A"]
    // ,["A","A","A","A","A","A"]
    // ,["A","A","A","A","A","A"]
    // ,["A","A","A","A","A","A"]
    // ,["A","A","A","A","A","B"]
    // ,["A","A","A","A","B","A"]]
};