Leetcode17：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.

Example:

Input: "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.

分析

部落客大概想了兩種方法，使用隊列或者遞歸，這裡隻介紹遞歸的做法，使用隊列的做法留給讀者思考。這道題比之前清華大學的某一道考研機試題目簡單，這道題好歹給出了手機的按鍵圖，不然有人記不得按鍵圖就直接gg了。

遞歸的做法很簡單，一位一位的周遊。在這之前，可以用一個全局變量記錄手機的按鍵分布，使用string數組即可，也可以使用map。用另一個全局變量記錄結果，在每次輸入時清空結果。首先從第一位數字開始周遊每一個字母，然後遞歸地周遊後續的數字，也就是循環和遞歸的結合。不過要注意，每周遊一個字母完成後，要将該字母從結果中删除，不然會影響到後續同級字母的周遊。最後，還需要注意輸入為空的情況，這時輸出也為空。

AC代碼如下：

string s[8] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
vector<string> re;//結果

class Solution {
public:
	int findsolution(string digits, int index, string result)
	{
		int num = digits[index] - '0';//string轉化為int
		string str = s[num-2];//注意數字與字母的對應
		int i = str.length();
		for(int j = 0; j < i; ++j)
		{
			result += str[j];
			if(index+1 >= digits.length())//注意一個是字元串長度，一個是字元串下标
			{
				re.push_back(result);//遞歸終止條件
			}
			else
			{
				findsolution(digits, index+1, result);//遞歸下一個數字
			}
            result.pop_back();//将目前字母彈出，周遊下一個同級字母
		}
		return 0;
	}
	
    vector<string> letterCombinations(string digits) {
        string result = "";
        re.clear();//清空結果
        if(digits.size() != 0)//判斷輸入是否為空，注意這裡最好使用size函數來判斷
        {
        	findsolution(digits, 0, result);//從第一個數字開始
		}
		return re;
    }
};