自己的解法

这个思路，其实就是逐个加入，加入以后形成一个字符串的列表，然后再用这个列表，去拼接后面字符。自己使用了迭代的思想，但是额外维护了一个临时数组，不然遍历的时候会出错。

class Solution {

    public List<String> letterCombinations(String digits) {

        List<String> res = new ArrayList<>();

        Map<Integer, String> numberMap = new HashMap<>(16);

        numberMap.put(2, "abc");

        numberMap.put(3, "def");

        numberMap.put(4, "ghi");

        numberMap.put(5, "jkl");

        numberMap.put(6, "mno");

        numberMap.put(7, "pqrs");

        numberMap.put(8, "tuv");

        numberMap.put(9, "wxyz");

        for (int i = 0; i < digits.length(); i++) {

            List<String> tempRes = new ArrayList<>();

            String s = numberMap.get(digits.charAt(i) - '0');

            for (int j = 0; j < s.length(); j++) {

                if (res.size() == 0) {

                    tempRes.add(String.valueOf(s.charAt(j)));            

                } else {

                    for (String m : res) {

                        tempRes.add(m + s.charAt(j));        

                    }

                }                        

            }

            res = tempRes;

        }

        return res;         

    }

}

官方解法

官方解法使用了递归，整体思路没变，就是一层一层往下递归，单个递归方法就是遍历当前数字对应的字符串，将字符添加到前面结果的后面。

class Solution {

  Map<String, String> phone = new HashMap<String, String>() {{

    put("2", "abc");

    put("3", "def");

    put("4", "ghi");

    put("5", "jkl");

    put("6", "mno");

    put("7", "pqrs");

    put("8", "tuv");

    put("9", "wxyz");

  }};

  List<String> output = new ArrayList<String>();

  public void backtrack(String combination, String next_digits) {

    // if there is no more digits to check

    if (next_digits.length() == 0) {

      // the combination is done

      output.add(combination);

    }

    // if there are still digits to check

    else {

      // iterate over all letters which map

      // the next available digit

      String digit = next_digits.substring(0, 1);

      String letters = phone.get(digit);

      for (int i = 0; i < letters.length(); i++) {

        String letter = phone.get(digit).substring(i, i + 1);

        // append the current letter to the combination

        // and proceed to the next digits

       // 隐藏了回溯的思想

        backtrack(combination + letter, next_digits.substring(1));

      }

    }

  }

  public List<String> letterCombinations(String digits) {

    if (digits.length() != 0)

      backtrack("", digits);

    return output;

  }

}