电话号码的字母之和

import java.util.ArrayList;

import java.util.HashMap;

import java.util.List;

import java.util.Map;

class Solution {

    /**

     * 使用多重循环实现

     */

    public List<String> letterCombinations(String digits) {

        // 如果为空，返回

        if ("".equals(digits)) return new ArrayList<>();

        // 初始化号码的字母

        Map<String, List<String>> map = new HashMap<>()<!--swig0-->);

            put("3", new ArrayList<>()<!--swig1-->);

            put("4", new ArrayList<>()<!--swig2-->);

            put("5", new ArrayList<>()<!--swig3-->);

            put("6", new ArrayList<>()<!--swig4-->);

            put("7", new ArrayList<>()<!--swig5-->);

            put("8", new ArrayList<>()<!--swig6-->);

            put("9", new ArrayList<>()<!--swig7-->);

        }};

        // 获取第一个号码的字母集

        List<String> result = map.get(digits.substring(0, 1));

        // 循环所有号码

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

            String key = digits.substring(i, i + 1);

            // 临时存储结果集

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

            // 双重循环遍历拼接字母

            for (String start : result){

                for (String end : map.get(key)){

                    temp.add(start + end);

                }

            }

            // 赋值

            result = temp;

        }

        return result;

    }

}

import java.util.ArrayList;

import java.util.HashMap;

import java.util.List;

import java.util.Map;

class Solution {

    /**

     * 采用回溯实现

     */

    public List<String> letterCombinations(String digits) {

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

        // 为空返回

        if ("".equals(digits)) return result;

        // 初始化号码的字母

        Map<String, List<String>> map = new HashMap<>()<!--swig8-->);

            put("3", new ArrayList<>()<!--swig9-->);

            put("4", new ArrayList<>()<!--swig10-->);

            put("5", new ArrayList<>()<!--swig11-->);

            put("6", new ArrayList<>()<!--swig12-->);

            put("7", new ArrayList<>()<!--swig13-->);

            put("8", new ArrayList<>()<!--swig14-->);

            put("9", new ArrayList<>()<!--swig15-->);

        }};

        // 递归

        recursion(map, result, digits, 0, new StringBuilder());

        return result;

    }

    private void recursion(Map<String, List<String>> map, List<String> result, String digits, int index, StringBuilder stringBuilder) {

        // 达到字母长度，存储结果集

        if (index == digits.length()){

            result.add(stringBuilder.toString());

        }else {

            // 循环当前字母集

            for (String value : map.get(digits.substring(index, index + 1))) {

                // 存储第一个字母

                stringBuilder.append(value);

                // 递归下一个字母集

                recursion(map, result, digits, index + 1, stringBuilder);

                // 回溯

                stringBuilder.deleteCharAt(index);

            }

        }

    }

}