17. Letter Combinations of a Pho

Description

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"].

Solution

• 递归调用

vector<string> letterCombinations(string digits) {
    vector<string> letters = {"", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    vector<string> ret;
    if (digits.length() == 0) {
        return ret;
    }
    this->dfsLetterCombinations(ret, "", digits, letters, 0);
    return ret;
}
void dfsLetterCombinations(vector<string>& ret, string path, string digits, vector<string> letters, int depth) {
    if (path.size() == digits.size()) {
        ret.push_back(path);
        return;
    }
    string curLetters = letters[digits[depth] - '1'];
    for (int i = 0; i < curLetters.size(); ++i) {
        this->dfsLetterCombinations(ret, path + curLetters[i], digits, letters, depth + 1);
    }
}

• 迭代法
  类似二叉树层次遍历，每经过一轮次，ret数组要在上一轮的基础上扩大3/4倍规模，借助curRet不断调整结果

vector<string> letterCombinations(string digits) {
    vector<string> letters = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    vector<string> ret;
    if (digits.size() == 0) {
        return ret;
    }
    ret.push_back("");
    for (int i = 0; i < digits.length(); ++i) {
        vector<string> curRet;
        string curLetters = letters[digits[i] - '0'];
        for (int j = 0; j < curLetters.length(); ++j) {
            for (int k = 0; k < ret.size(); ++k) {
                curRet.push_back(ret[k] + curLetters[j]);
            }
        }
        ret = curRet;
    }
    return ret;
}