17. Letter Combinations of a Phone Number
in 剑指offer with 0 comment

17. Letter Combinations of a Phone Number

in 剑指offer with 0 comment

题目大意:对于一个给出的数字串,输出其可能的在手机键盘上代表的字符串,如对于数字串“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"};
Responses

From now on, bravely dream and run toward that dream.
陕ICP备17001447号