时间轴

2025-11-27

init

题目：

P17 回溯

https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/?envType=study-plan-v2&envId=top-interview-150

回溯

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
37
38
39
40
41
42
43
44
#include <vector>
#include <string>
#include <unordered_map>
using std::vector;
using std::string;
using std::unordered_map;

const string digit2alpha[] = { [0] = { "" },	[1] = { "" },	 [2] = { "abc" },  [3] = { "def" }, [4] = { "ghi" },
			       [5] = { "jkl" }, [6] = { "mno" }, [7] = { "pqrs" }, [8] = { "tuv" }, [9] = { "wxyz" } };
class Solution {
    public:
	void backtrace(string &digits, string &track, vector<string> &res)
	{
		if (track.size() == digits.size()) {
			res.push_back(track);
			return;
		}
		string curr_alpha;
		char ch = digits[track.size()];
		int i;

		curr_alpha = digit2alpha[ch - '0'];

		for (i = 0; i < curr_alpha.size(); i++) {
			// // 跳过已经选择过的避免重复
			// if (track.find(curr_alpha[i]) != string::npos) {
			// 	continue;
			// }
			// 加入选择
			track.push_back(curr_alpha[i]);
			// 进入下一层决策树
			backtrace(digits, track, res);
			// 取消选择
			track.pop_back();
		}
	}
	vector<string> letterCombinations(string digits)
	{
		vector<string> res;
		string track;
		backtrace(digits, track, res);
		return res;
	}
};

leetcode hot100 rewrite

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <vector>
#include <string>

using std::vector;
using std::string;

class Solution {
    private:
        vector<vector<char> > num2char = {
                {},
                {},
                { 'a', 'b', 'c' },
                { 'd', 'e', 'f' },
                { 'g', 'h', 'i' },
                { 'j', 'k', 'l' },
                { 'm', 'n', 'o' },
                { 'p', 'q', 'r', 's' },
                { 't', 'u', 'v' },
                { 'w', 'x', 'y', 'z' },
        };

        void __letterCombinations(vector<int> &nums, vector<string> &res, string &curr, int pos)
        {
                int i, n = nums.size();

                if (curr.size() == n) {
                        res.push_back(curr);
                        return;
                }

                for (char ch : num2char[nums[pos]]) {
                        curr.push_back(ch);

                        __letterCombinations(nums, res, curr, pos + 1);

                        curr.pop_back();
                }
        }

    public:
        vector<string> letterCombinations(string digits)
        {
                vector<string> res;
                vector<int> nums;
                string curr;

                for (char ch : digits)
                        nums.push_back(ch - '0');

                __letterCombinations(nums, res, curr, 0);

                return res;
        }
};