LeetCode: Letter Combinations of a Phone Number

By | 2012 年 9 月 29 日

Letter Combinations of a Phone Number
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.

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.

Analyze

Process the digits one by one, for each digits, append the possible characters to the existing strings. For example, if input is “23”.

For digit 2, the possible chars are a, b, c. So after this step we have a list of ['a', 'b', 'c']

For digit 3, the possible chars are d, e, f. So for each existing strings in the list, append each char to all of them. So for d we have ad, bd, cd, for e we have ae, be, ce; for f we have af, bf, cf. Combine them together, got the list of: ['ad', 'bd', 'cd', 'ae', 'be', 'ce', 'af', 'bf', 'cf']

Solutions

Ruby

MAP = {
    '2' => 'abc',
    '3' => 'def',
    '4' => 'ghi',
    '5' => 'jkl',
    '6' => 'mno',
    '7' => 'pqrs',
    '8' => 'tuv',
    '9' => 'wxyz'
    }
# @param {String} digits
# @return {String[]}
def letter_combinations(digits)
    results = [''] # add the seed
    digits.each_char do |digit|
        chars = MAP[digit]
        results = results.map{|item| chars.each_char.map{|c| item + c} }.flatten
    end
    results.delete('') # delete the seed if still there
    results
end

C++

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<char> >map(10);
        map[0] = vector<char>(1);

        map[0][0] = ' ';
        map[1] = vector<char>(1);
        map[1][0] = ' ';

        map[2] = vector<char>(3);
        map[2][0] = 'a';
        map[2][1] = 'b';
        map[2][2] = 'c';

        map[3] = vector<char>(3);
        map[3][0] = 'd';
        map[3][1] = 'e';
        map[3][2] = 'f';

        map[4] = vector<char>(3);
        map[4][0] = 'g';
        map[4][1] = 'h';
        map[4][2] = 'i';

        map[5] = vector<char>(3);
        map[5][0] = 'j';
        map[5][1] = 'k';
        map[5][2] = 'l';

        map[6] = vector<char>(3);
        map[6][0] = 'm';
        map[6][1] = 'n';
        map[6][2] = 'o';

        map[7] = vector<char>(4);
        map[7][0] = 'p';
        map[7][1] = 'q';
        map[7][2] = 'r';
        map[7][3] = 's';

        map[8] = vector<char>(3);
        map[8][0] = 't';
        map[8][1] = 'u';
        map[8][2] = 'v';

        map[9] = vector<char>(4);
        map[9][0] = 'w';
        map[9][1] = 'x';
        map[9][2] = 'y';
        map[9][3] = 'z';

        vector<string> result;
        result.push_back("");
        for(int idigit = 0; idigit < digits.size(); ++ idigit) {
            char di = digits[idigit];
            int index = di - '0';
            if(index < 0 || index > 9)
                continue;
            vector<char> &dmap = map[index];
            int curSize = result.size();
            int times = dmap.size();
            for(int itime = 0; itime < times - 1; ++itime) {
                for(int itemp = 0; itemp < curSize; ++itemp) {
                    result.push_back(result[itemp]);
                }
            }
            for(int itime = 0; itime < times ; ++itime) {
                char append = dmap[itime];
                for(int itemp = 0; itemp < curSize; ++itemp) {
                    int itemIndex = itime * curSize + itemp;
                    if(itemIndex >= result.size()) {
                        cout<<"d";
                        continue;
                    }
                    result[itemIndex].push_back(append);
                }
            }
        }
        return result;
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注