17LetterCombinationsofaPhoneNumber.org

[#B] 17 Letter Combinations of a Phone Number - LeetCode

题目

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.

思路：

每个数字对应3或4个字母，通过回溯把每种情况考虑进去。找出每个数字对应的字母，一个一个的累加到前面的结果中。

Java

class Solution {
 
    List<String> res = new ArrayList();
 
    String[] lettersMap = {
        " ",
        "",
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz"
    };
 
    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.isEmpty()) return res;
        findCombinations(digits, 0, "");
        return res;
    }
 
    public void findCombinations(String digits, int index, String s) {
        if (index == digits.length()) {
            res.add(s);
            return;
        }
     
        char c = digits.charAt(index);
        String letter = lettersMap[c - '0'];
        for (int i = 0; i < letter.length(); i++) {
            findCombinations(digits, index + 1, s + letter.charAt(i));
        }
     
    }
}

CPP

class Solution {
private:
    vector<string> res;    
 
    const string letterMap[10] = {
        " ",
        "",
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz"
    };
 
    void findCombination(const string &digits, int index, const string &s) {
        if (index == digits.size()) {
            res.push_back(s);
            return;
        }
     
        char c = digits[index];
        string letters = letterMap[c - '0'];
        for (int i = 0; i < letters.size(); i++) {
            findCombination(digits, index + 1, s + letters[i]);
        }
        return;
    }
 
 
public:
    vector<string> letterCombinations(string digits) {
        if (digits == "") {
            return res;
        }
        findCombination(digits, 0, "");
        return res;
    }
 
};