时间轴

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