Leetcode-17 Letter Combinations of a Phone Number

发表于 | 分类于 | 次

Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Note: Although the above answer is in lexicographical order, your answer could be in any order you want.

Example 1

1
2
Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

解题思路

每个数字对应一系列字母，从前往后遍历数字，将数字替换为字母。因为每个数字替换有多种选择，很容易想到回溯法。每当树的一层被完全展开（即完成所有替换选择），便回到上一层做下一个选择并展开。

复杂度分析

  • 时间复杂度：$O(m^n)$，m 为每个数字对应的最大字母数量。
  • 空间复杂度：$O(n)$，除去返回结果，只用了一个额外的字符串。

代码

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<string> letterCombinations(string digits) {
		if (digits.empty()) return res;
		string s(digits);
		backtrack(digits, 0, s);
		return res;
	}

private:
	vector<string> mp = { "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };
	vector<string> res;

	void backtrack(const string &digits, int level, string &s) {
		if (level == digits.size()) {
			res.push_back(s);
			return;
		}
		int id = digits[level] - 48;
		for (char c : mp[id]) {
			s[level] = c;
			backtrack(digits, level + 1, s);
		}
	}
};