017. Letter Combinations of a Phone Number

题目大意：对于一个给出的数字串，输出其可能的在手机键盘上代表的字符串，如对于数字串“23”。

其可能代表的字符串便有”ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”

题目链接

17. Letter Combinations of a Phone Number

switch

一个for一个switch，应该可以解决问题。

class Solution {
public:
	vector<string> letterCombinations(string digits) {
		vector<string> two = { "a","b","c" };
		vector<string> three = { "d","e","f" };
		vector<string> four = { "g","h","i" };
		vector<string> five = { "j","k","l" };
		vector<string> six = { "m","n","o" };
		vector<string> seven = { "p","q","r","s" };
		vector<string> eight = { "t","u","v" };
		vector<string> nine = { "w","x","y","z" };
		vector<string> answer = {};
		vector<string> temp = {};
		for (int i = 0; i < digits.size(); i++) {
			switch (digits[i])
			{
			case '1':
				break;
			case '0':
				break;
			case '2': {
				if (!answer.size()) {
					for (int i = 0; i < two.size(); i++) 
						answer.push_back(two[i]);					
					break;
				}
				temp = answer;
				answer.clear();
				for (int i = 0; i < temp.size(); i++) {
					for (int j = 0; j < two.size(); j++) {
						answer.push_back(temp[i] + two[j]);
					}
				}
				break;
			}
			case '3': {
				if (!answer.size()) {
					for (int i = 0; i < three.size(); i++)
						answer.push_back(three[i]);
					break;
				}
				temp = answer;
				answer.clear();
				for (int i = 0; i < temp.size(); i++) {
					for (int j = 0; j < three.size(); j++) {
						answer.push_back(temp[i] + three[j]);
					}
				}
				break;
			}
			case '4': {
				if (!answer.size()) {
					for (int i = 0; i < four.size(); i++)
						answer.push_back(four[i]);
					break;
				}
				temp = answer;
				answer.clear();
				for (int i = 0; i < temp.size(); i++) {
					for (int j = 0; j < four.size(); j++) {
						answer.push_back(temp[i] + four[j]);
					}
				}
				break;
			}
			case '5': {
				if (!answer.size()) {
					for (int i = 0; i < five.size(); i++)
						answer.push_back(five[i]);
					break;
				}
				temp = answer;
				answer.clear();
				for (int i = 0; i < temp.size(); i++) {
					for (int j = 0; j < five.size(); j++) {
						answer.push_back(temp[i] + five[j]);
					}
				}
				break;
			}
			case '6': {
				if (!answer.size()) {
					for (int i = 0; i < six.size(); i++)
						answer.push_back(six[i]);
					break;
				}
				temp = answer;
				answer.clear();
				for (int i = 0; i < temp.size(); i++) {
					for (int j = 0; j < six.size(); j++) {
						answer.push_back(temp[i] + six[j]);
					}
				}
				break;
			}
			case '7': {
				if (!answer.size()) {
					for (int i = 0; i < seven.size(); i++)
						answer.push_back(seven[i]);
					break;
				}
				temp = answer;
				answer.clear();
				for (int i = 0; i < temp.size(); i++) {
					for (int j = 0; j < seven.size(); j++) {
						answer.push_back(temp[i] + seven[j]);
					}
				}
				break;
			}
			case '8': {
				if (!answer.size()) {
					for (int i = 0; i < eight.size(); i++)
						answer.push_back(eight[i]);
					break;
				}
				temp = answer;
				answer.clear();
				for (int i = 0; i < temp.size(); i++) {
					for (int j = 0; j < eight.size(); j++) {
						answer.push_back(temp[i] + eight[j]);
					}
				}
				break;
			}
			case '9': {
				if (!answer.size()) {
					for (int i = 0; i < nine.size(); i++)
						answer.push_back(nine[i]);
					break;
				}
				temp = answer;
				answer.clear();
				for (int i = 0; i < temp.size(); i++) {
					for (int j = 0; j < nine.size(); j++) {
						answer.push_back(temp[i] + nine[j]);
					}
				}
				break;
			}
			default:
				break;
			}
		}
		return answer;

	}
};

代码看起来挺奇怪的。。。。一点没有刷leetcode的快感。

略微洋气

class Solution {
public:
    static const string map[10];
    vector<string> letterCombinations(string digits) {
        vector<string> ans;
        if (digits.length() > 0) {
            // 先去掉第一位，变成一个规模小1的问题以递归解决
            vector<string> tmp = letterCombinations(digits.substr(1, digits.length() - 1));
            // 处理边界情况
            if (tmp.size() == 0) {
                tmp.push_back("");
            }
            // 在递归计算出的答案前添加上所有第0位可能对应的字母来组成新的答案集
            for (int i = 0; i < map[digits[0] - '0'].length(); i++) {
                for (int j = 0; j < tmp.size(); j++) {
                    ans.push_back(map[digits[0] - '0'][i] + tmp[j]);
                }
            }
        }
        return ans;
    }
};

// 对应表
const string Solution::map[] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};