一：电话号码的字母组合

image-20251011111051203

1. 回溯

这道题的思路和子集很相似，不过需要使用哈希表处理映射关系

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    vector<string> ans;
    string sub;
    unordered_map<char, string> map{
            {'2', "abc"},
            {'3', "def"},
            {'4', "ghi"},
            {'5', "jkl"},
            {'6', "mno"},
            {'7', "pqrs"},
            {'8', "tuv"},
            {'9', "wxyz"}
        };
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return ans;
        recursion(digits, 0);
        return ans;
    }
    void recursion(string& digits, int cur)
    {
        if (cur == digits.size())
        {
            ans.emplace_back(sub);
            return;
        }
        char ch = digits[cur];
        auto& subLetter = map.at(ch);
        for (auto& ch : subLetter)
        {
            sub.push_back(ch);
            recursion(digits, cur + 1);
            sub.pop_back();
        }
    }
};

image-20251011111115164

二：组合总和

image-20251012164907817

1. 搜索回溯

这道题的思路也和子集很相似，区别在于子集只有选和不选，必须进入下一层，而当前题目可以包含重复值，可以一直选择一个元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> ans;
        vector<int> temp;
        recursion(candidates, target - 0, ans, temp, 0);
        return ans;
    }
    void recursion(vector<int>& candidates, int&& target, vector<vector<int>>& ans, vector<int>& temp, int cur)
    {
        if (cur == candidates.size()) return;
        if (target == 0)
        {
            ans.emplace_back(temp);
            return;
        }
        recursion(candidates, target - 0, ans, temp, cur + 1);      // 跳过
        if (target - candidates[cur] >= 0)
        {
            temp.emplace_back(candidates[cur]);     // 选择
            recursion(candidates, target - candidates[cur], ans, temp, cur);      // 下一层
            temp.pop_back();
        }
    }
};

image-20251012164933750

三：括号生成

image-20251012172114814

1. 暴力

使用暴力将所有组合生成并检测是否是有效字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        string cur;
        gengerateAll(ans, cur, n * 2);       // 有double的字符
        return ans;
    }
    void gengerateAll(vector<string>& ans, string& cur, int n)
    {
        if (cur.size() == n)        // 一个完整的字符串
        {
            if (isValid(cur)) ans.emplace_back(cur);
            return;
        }
        cur.push_back('(');
        gengerateAll(ans, cur, n);
        cur.pop_back();
        cur.push_back(')');
        gengerateAll(ans, cur, n);
        cur.pop_back();
    }
    bool isValid(string& str)
    {
        int index = 0;
        for (auto& ch : str)
        {
            if (ch == '(') ++index;     // 左括号加一，右括号减一
            else --index;
            if (index < 0) return false;        // 说明前面的字符串右括号多于左括号，肯定不是有效字符串
        }
        return index == 0;
    }
};

image-20251012172236977

2. 回溯

暴力充斥了很多无效的字符串直到最后才做判断，可以在递归过程中就对字符串进行检查

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        string cur;
        gengerateAll(ans, cur, n * 2, 0, 0);       // 有double的字符
        return ans;
    }
    void gengerateAll(vector<string>& ans, string& cur, int n, int left, int right)
    {
        if (cur.size() == n)        // 一个完整的字符串
        {
            ans.emplace_back(cur);
            return;
        }
        if (left < n / 2)
        {
            cur.push_back('(');
            gengerateAll(ans, cur, n, left + 1, right);
            cur.pop_back();
        }
        if (right < left)
        {   
            cur.push_back(')');
            gengerateAll(ans, cur, n, left, right + 1);
            cur.pop_back();
        }
    }
};

image-20251012172229201

3. 按括号序列的长度递归

每个有效字符串必是’(‘开头，某个’)'结尾，其组成为“(A)B”，A的可能性为i对，则B为n-i-1对

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    shared_ptr<vector<string>> cache[10] = {nullptr};
    vector<string> generateParenthesis(int n) {
        return *generate(n);
    }
    shared_ptr<vector<string>> generate(int n) {
        if (cache[n] != nullptr)
            return cache[n];
        if (n == 0) {
            cache[0] = shared_ptr<vector<string>>(new vector<string>{""});
        } else {
            auto result = shared_ptr<vector<string>>(new vector<string>);
            for (int i = 0; i != n; ++i) {
                auto lefts = generate(i);
                auto rights = generate(n - i - 1);
                for (const string& left : *lefts)
                    for (const string& right : *rights)
                        result -> push_back("(" + left + ")" + right);
            }
            cache[n] = result;
        }
        return cache[n];
    }
};

image-20251012172219771

四：单词搜索

image-20251013172320631

1. 回溯

使用dfs来逐个访问节点，已访问的需要标记，并在访问后恢复，因为后续还会访问

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int row = board.size();
        int col = board[0].size();
        vector<vector<int>> visited(row, vector<int>(col));
        for (int i = 0; i < row; ++i)
            for (int j = 0; j < col; ++j)
                if (recursion(board, visited, i, j, word, 0)) return true;
        return false;
    }
    bool recursion(vector<vector<char>>& board, vector<vector<int>>& visited, int i, int j, string& word, int cur)
    {
        if (board[i][j] != word[cur]) return false;
        else if (cur == word.size() - 1) return true;		// 应当减少size的调用
        visited[i][j] = 1;		 // 原地标记更快，不需要额外内存
        vector<pair<int, int>> directions{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};		// 这里可使用static提高运行速度
        for (auto& dir : directions)
        {
            int newi = i + dir.first;
            int newj = j + dir.second;
            if (newi >= 0 && newi < board.size() && newj >= 0 && newj < board[0].size())
                if (!visited[newi][newj])
                    if (recursion(board, visited, newi, newj, word, cur + 1)) return true;
        }
        visited[i][j] = 0;
        return false;
    }
};

image-20251013204447559

五：分割回文串

image-20251013233435064

1. 回溯+动态规划

本题的难点在于状态转移方程

image-20251014094422549

image-20251014094438404

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    vector<vector<string>> result;
    vector<vector<int>> flag;
    vector<string> cur;
    int len;
    vector<vector<string>> partition(string s) {
        len = s.size();
        flag.assign(len, vector<int>(len, true));
        for (int i = len - 1; i >= 0; --i)
            for (int j = i + 1; j < len; ++j)
                flag[i][j] = (s[i] == s[j]) && flag[i + 1][j - 1];        // i需要减，j需要加，形成上三角矩阵，这是本题的关键
        recursion(s, 0);
        return result;
    }
    void recursion(string& s, int i)
    {
        if (i == len) 
        {
            result.emplace_back(cur);
            return;
        }
        for (int j = i; j < len; ++j)
        {
            if (flag[i][j])
            {
                cur.emplace_back(s.substr(i, j + 1 - i));
                recursion(s, j + 1);
                cur.pop_back();
            }
        }
    }
};

image-20251013233528545

2. 回溯+记忆化搜索

这里不使用数组来表示子字符串的状态，而是在递归时不断更新

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    vector<vector<string>> result;
    vector<vector<int>> flag;
    vector<string> cur;
    int len;
    vector<vector<string>> partition(string s) {
        len = s.size();
        flag.assign(len, vector<int>(len));
        recursion(s, 0);
        return result;
    }
    void recursion(string& s, int i)
    {
        if (i == len) 
        {
            result.emplace_back(cur);
            return;
        }
        for (int j = i; j < len; ++j)
        {
            if (IsPalindrome(s, i, j) == 1)
            {
                cur.emplace_back(s.substr(i, j + 1 - i));
                recursion(s, j + 1);
                cur.pop_back();
            }
        }
    }
    int IsPalindrome(string& s, int i, int j)      // 0 、1、-1
    {
        if (flag[i][j]) return flag[i][j];
        if (i >= j) return flag[i][j] = 1;
        return flag[i][j] = (s[i] == s[j] ? IsPalindrome(s, i + 1, j - 1) : -1);
    }
};

image-20251013233537461