[LeetCode] 17、电话号码的字母组合

题目描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例：

输入：“23”
输出：[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].

参考代码

常规排列组合问题

class Solution {
public:
	vector<string> letterCombinations(string digits) {
		vector<string> res;
		int length = digits.length();
		if (length == 0)
			return res;

		umap['2'] = "abc";
		umap['3'] = "def";
		umap['4'] = "ghi";
		umap['5'] = "jkl";
		umap['6'] = "mno";
		umap['7'] = "pqrs";
		umap['8'] = "tuv";
		umap['9'] = "wxyz";

		string str(length, '*');
		for (int i = 0; i < umap[digits[0]].length(); i++) {
			str[0] = umap[digits[0]][i];
			letterCombinationsRecursively(digits, str, res, 1);
		}

		return res;
	}

	void letterCombinationsRecursively(string &digits, string &str,
		vector<string> &res, int nextIndex) {
		if (nextIndex == digits.length()) {
			res.push_back(str);
			return;
		}

		for (int i = 0; i < umap[digits[nextIndex]].length(); i++) {
			str[nextIndex] = umap[digits[nextIndex]][i];
			letterCombinationsRecursively(digits, str, res, nextIndex + 1);
		}
	}

private:
	unordered_map<char, string> umap;
};