Java描述 LeetCode，17. Letter Combinations of a Phone Number 电话号码的组合数

푰’풎 풉풉품, 푰 풂풎 풂 품풓풂풅풖풂풕풆 풔풕풖풅풆풏풕 풇풓풐풎 푵풂풏풋풊풏품, 푪풉풊풏풂.

 푺풉풄풐풐풍: 푯풐풉풂풊 푼풏풊풗풆풓풔풊풕풚 푳풆풂풓풏풊풏품: 푰’풎 풄풖풓풓풆풏풕풍풚 풍풆풂풓풏풊풏품 풅풆풔풊품풏 풑풂풕풕풆풓풏, 푳풆풆풕풄풐풅풆, 풅풊풔풕풓풊풃풖풕풆풅 풔풚풔풕풆풎, 풎풊풅풅풍풆풘풂풓풆 풂풏풅 풔풐 풐풏. 푯풐풘 풕풐 풓풆풂풄풉 풎풆：푽푿 푴풚 풃풍풐품: 풉풕풕풑풔://풉풉품풚풚풅풔.풃풍풐품.풄풔풅풏.풏풆풕/ 푷풓풐풇풆풔풔풊풐풏풂풍 풔풌풊풍풍풔：풎풚 풅풓풆풂풎
1-1：题目

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

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 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:

Input: digits = ""
Output: []

Example 3:

Input: digits = "2"
Output: ["a","b","c"]

Constraints:

0 <= digits.length <= 4
digits[i] is a digit in the range ['2', '9'].

通过次数401,448提交次数696,748

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题和之前的回溯解法差不多，主要是细节部分是有点烦人的。全局来看就相当于两层循环，有两个索引，一个是map中的索引map_index，一个是digits里面的索引digits_index，核心思路就是用索引digits_index来控制输入的数挨个提取int map_index = digits.charAt(digits_index) - '0' - 2;，提出来就可以通过它去找到对应的字符数组map[map_index]，对这里面的字符挨个去遍历，遍历完了之后digits_index+1，找下一个遍历的字符数组map[map_index]，依次类推。代码如下：

List result = new ArrayList<>();
String[] map = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
StringBuilder builder = new StringBuilder();

public List letterCombinations(String digits) {
    int n = digits.length();
    if (n == 0) {
        return result;
    }
    this.backTracking(0, n, digits);
    return result;
}


public void backTracking(int digits_index, int end, String digits) {
    if (digits_index == end) {
        result.add(builder.toString());
        return;
    }
    int map_index = digits.charAt(digits_index) - '0' - 2;
    for (int i = 0; i < map[map_index].length(); i++) {
        builder.append(map[map_index].charAt(i));
        backTracking(digits_index + 1, end, digits);
        builder.deleteCharAt(builder.length() - 1);
    }
}

需要注意的点：

先将数字和字符数组对应起来, map也行，其实map是更好操作的，不需要进行char to int的转换，方便很多。对digits是按索引进行遍历的，因为digits里面的2,3等字符是可能重复的= =，这也要注意。我没注意到。结束的条件也要注意，对digits中的字符挨个遍历的时候，结束的条件是digits_index == end。遍历是按照digits里面的数字字符遍历的，而不是直接去map里面一个一个遍历，这个是我做前两道题目做僵化了导致的后果。。