本文共 2726 字，大约阅读时间需要 9 分钟。

题目

地址：

https://leetcode.com/problems/letter-combinations-of-a-phone-number/

描述:

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.

此题目用回溯解法，遍历数组所有解，注意递归的退出条件。

遍历解法

顺序执行分解：

1. 初始化二维数组char[][] map， 存储数字以及字母的关系，map[digit - '2'] 获取字母数组。
2. 遍历上一次的字符串List，遍历并拼接新的字符(字符从遍历字符数组所得)。

public List
   
     letterCombinationWithIterate(String digits) {
       List
    
      result = new ArrayList<>();    if (digits == null || digits.length() == 0) {
         return result;    }    char[][] map = new char[8][];    map[0] = "abc".toCharArray();    map[1] = "def".toCharArray();    map[2] = "ghi".toCharArray();    map[3] = "jkl".toCharArray();    map[4] = "mno".toCharArray();    map[5] = "pqrs".toCharArray();    map[6] = "tuv".toCharArray();    map[7] = "wxyz".toCharArray();    result.add("");    for (char digit: digits.toCharArray()) {
         result = append(result, map[digit - '2']);    }    System.out.println("result > " + Arrays.toString(result.toArray()));    return result;  }  private List
     
       append(List
      
        lastList, char[] charArray) {
       List
       
          nextList = new ArrayList<>();    for (String s: lastList) {
         for (char c: charArray) {
           nextList.add(s + c);      }    }    return nextList;  }
       
      
     
    
   

回溯解法

回溯分解：

1. 回溯出口为nextDigits == null || nextDigits.length() == 0，
2. combination为累计拼接的结果

Map
   
     phone = new HashMap
    
     () {
   {
       put('2', "abc");    put('3', "def");    put('4', "ghi");    put('5', "jkl");    put('6', "mno");    put('7', "pqrs");    put('8', "tuv");    put('9', "wxyz");  }};  private List
     
       resultList = new ArrayList<>();  public List
      
        letterCombinationsWithBacktrack(String digits) {
       if (digits == null || digits.length() == 0) {
         return resultList;    }    backTrack("", digits);    return resultList;  }  public void backTrack(String combination, String nextDigits) {
       if (nextDigits == null || nextDigits.length() == 0) {
         resultList.add(combination);      return;    }    char c = nextDigits.charAt(0);    for (char item: phone.get(c).toCharArray()) {
         backTrack(combination + item, nextDigits.substring(1));    }  }
      
     
    
   

代码下载

https://github.com/zgpeace/awesome-java-leetcode/blob/master/code/LeetCode/src/backtracking/LetterCombinationsOfAPhoneNumber.java

转载地址：http://plazk.baihongyu.com/