LeetCode刷题（C++）——Letter Combinations of a Phone Number（Medium）

系统管理员 2022-06-16 05:30 122阅读 0赞

Given a digit string, 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.

![200px-Telephone-keypad2.svg.png][]

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

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

思路：第一眼看到这道题觉得不难，只需要利用for循环暴力寻找所有的组合结果就可以了，但是仔细一想发现，我们事先不知道digits的大小，于是就无法确定使用for循环的层数。怎么办呢？嗯，可以用递归来代替for循环。那么递归我们要递归什么呢？当然是要递归digits中的数字啦，然后对每个数字对应的字符进行遍历，来组合所有的可能。

class Solution {
    public:
        vector<string> letterCombinations(string digits) {
            vector<string> letter;
    		if (digits.empty())
    			return letter;
    		vector<string> num = { "abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };
    		string let;
    		dfs(digits, letter, let, 0, num);
    		return letter;
    	}
    
    	void dfs(string& digits, vector<string>& letter, string& let, int pos, vector<string> num)
    	{
    		if (pos == digits.size())
    		{
    			letter.push_back(let);
    			return;
    		}
    		int x = (digits[pos] - '0') - 2;
    		string s = num[x];
    		for (int i = 0; i < s.size();i++)
    		{
    			let.push_back(s[i]);
    			dfs(digits, letter, let, pos + 1, num);
    			let.pop_back();
    		}
        }
    };

[200px-Telephone-keypad2.svg.png]: /images/20220616/5f32cc6906014cee8872e4e6676300d3.png