17.md

17. Letter Combinations of a Phone Number

Leetcode link

解题思路

本题要我们求出指定的拨号能够组合出的所有字母排列

要处理这个题目首先需要建立一组拨号数字到字母的映射表

dialMap = {
  2: 'abc',
  3: 'def',
  4: 'ghi',
  5: 'jkl',
  6: 'mno',
  7: 'pqrs',
  8: 'tuv',
  9: 'wxyz'
}

然后我们可以抽象一下：所有拨号字母的组合 = 前面 n 个拨号字母的组合 分别加上 后面一个拨号的字母映射

举个例子，假设现在要求 "23"，那么：

• 2 的组合有：["a", "b", "c"]
• 将 3 的字母映射分别加到 2 的组合中：["ad", "bd", "cd", "ae", "be", "ce", "af", "bf", "cf"]

如此一来，我们只需要遍历 digits，然后每次都将新的数字的映射分别加到旧的组合后面就好了

C++

class Solution {
public:
    vector<string> combineString(vector<string> & prev, string cur) {
        vector<string> res;
        for(string comb : prev) {
            for(char ch: cur) {
                res.push_back(comb + ch);
            }
        }
        return res;
    }
    vector<string> letterCombinations(string digits) {
        if(digits.size() == 0) {
            return {};
        }
        unordered_map<int, string> dialMap {
            {'2', "abc"},
            {'3', "def"},
            {'4', "ghi"},
            {'5', "jkl"},
            {'6', "mno"},
            {'7', "pqrs"},
            {'8', "tuv"},
            {'9', "wxyz"}
        };
        vector<string> res {""};
        for(char digit: digits) {
            res = combineString(res, dialMap[digit]);
        }
        return res;
    }
    
};

Javascript

var letterCombinations = function(digits) {
    const dialMap = {
        2: 'abc',
        3: 'def',
        4: 'ghi',
        5: 'jkl',
        6: 'mno',
        7: 'pqrs',
        8: 'tuv',
        9: 'wxyz'
    }
    return digits.split('').reduce((prev, cur)=> {
        if(prev.length === 0) {
            return dialMap[cur].split('');
        }
        let res = [];
        for(let oldChar of prev) {
            for(let newChar of dialMap[cur].split('')) {
                res.push(`${oldChar}${newChar}`);
            }
        }
        return res;
    },[])
};