17. 电话号码的字母组合

[MyLinChi]

题目描述

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

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

示例:

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number

解决方案

采用递归调用进行深度优先搜索的方法返回所有的待求字符串，字符串的长度应该跟输入字符串长度是一样的，对应于搜索树的深度。其中的dfs函数的作用是在给定path的情况下往下搜索，若符合条件则返回。

class Solution {
public:
	vector<string> res;//结果字符串集
	string digits;//输入字符串
	vector<string> dic; 
	void dfs(string path,int depth){	//path-当前的路径,depth-当前结点的深度
		if (depth == digits.length()){
			if(path !="")res.push_back(path);
			return;
		}
		int index = digits[depth] - '0';
		string str = dic[index];
		int len = str.size();
		for (int i = 0; i < len; i++){
			dfs(path + str[i],depth+1);
		}
	}
	vector<string> letterCombinations(string digits) {
		res = {};
		dic = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
		this->digits = digits;
		dfs("",0);
		return this->res;
	}
};