LeetCode 17 Letter Combinations of a Phone Number

/*
 * @lc app=leetcode id=17 lang=cpp
 *
 * [17] Letter Combinations of a Phone Number
 *
 * https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/
 *
 * algorithms
 * Medium (40.64%)
 * Total Accepted:    360.2K
 * Total Submissions: 883.9K
 * Testcase Example:  '"23"'
 *
 * 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.
 * 
 */
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> answer;

        if(digits == "") return answer;
        vector<string> dict(10);
        dict[2] = "abc";
        dict[3] = "def";
        dict[4] = "ghi";
        dict[5] = "jkl";
        dict[6] = "mno";
        dict[7] = "pqrs";
        dict[8] = "tuv";
        dict[9] = "wxyz";

        answer.push_back("");
        for(int i = 0;i < digits.length(); ++i){
            int origin = answer.size();

            int len = dict[digits[i] - '0'].length();

            if(!len) continue;

            answer.resize(answer.size()*len);
            for(int j = len;j > 0;--j){
                for(int k = 0;k < origin;++k){
                    answer[origin*j + k - origin] = answer[k] + dict[digits[i] - '0'][j-1];
                }
            }
        }
        return answer;
    }
};

这位兄台 的解法更巧妙，每次erase一个，添加3到四个。