017 - Letter Combinations of a Phone Number

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.
Hide Tags
Backtracking String
Hide Similar Problems
(M) Generate Parentheses (M) Combination Sum


穷举，没啥好说的。
字符串也可以 push_back, pop_back， 好玩。

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> rst;
        string buf="";
        int ld = digits.length();
        if(ld)
            build(digits, ld, 0, buf, rst);
        return rst;
    }

private:
    string mapping[10] = {" ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };

    void build(string digits, int ld, int pos, string& buf, vector<string>& rst)
    {
        if(ld == pos)
            rst.push_back(buf);
        else
        {
            int id = digits[pos]-'0';
            int lm = mapping[id].length();
            for(int mm=0; mm<lm; ++mm)
            {
                buf.push_back((mapping[id])[mm]);    //same as "buf += (mapping[id])[mm];"
                build(digits, ld, pos+1, buf, rst);
                buf.pop_back();
            }
        }
        return;
    }
};

0 ms.