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

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 ：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

解法：

package leetcode2;

import java.util.*;

/**
 * 2021/3/9 15:54
 *
 * @Author ayue
 */
public class Solution17 {
    public List<String> letterCombinations(String digits) {//队列解法，前出后进
        List<String> strings = new LinkedList<String>();
        Map<Character, String[]> map = new HashMap<Character, String[]>() {{    //存储为数组更好操作
            put('2', new String[]{"a", "b", "c"});
            put('3', new String[]{"d", "e", "f"});
            put('4', new String[]{"g", "h", "i"});
            put('5', new String[]{"j", "k", "l"});
            put('6', new String[]{"m", "n", "o"});
            put('7', new String[]{"p", "q", "r", "s"});
            put('8', new String[]{"t", "u", "v"});
            put('9', new String[]{"w", "x", "y", "z"});
        }};
        Queue<String> queue = new LinkedList<String>();
        char[] chars = digits.toCharArray();
        for (char c : chars) {
            spli(queue, map.get(c));
        }
        for (String q : queue) {
            strings.add(q);
        }
        
        return strings;
    }
    
    private void spli(Queue<String> queue, String[] strings) {
        if (queue.size() == 0) {
            for (String s : strings) {
                queue.add(s);
            }
        } else {
            int queueLen = queue.size();
            for (int i = 0; i < queueLen; ++i) {
                String str = queue.poll();
                for (String s : strings) {
                    queue.add(str + s);
                }
            }
        }
    }
    
    public List<String> letterCombinations2(String digits) {//回溯。遍历
        List<String> strings = new LinkedList<String>();
        if (digits.length() == 0) {
            return strings;
        }
        Map<Character, String[]> map = new HashMap<Character, String[]>() {{    //存储为数组更好操作
            put('2', new String[]{"a", "b", "c"});
            put('3', new String[]{"d", "e", "f"});
            put('4', new String[]{"g", "h", "i"});
            put('5', new String[]{"j", "k", "l"});
            put('6', new String[]{"m", "n", "o"});
            put('7', new String[]{"p", "q", "r", "s"});
            put('8', new String[]{"t", "u", "v"});
            put('9', new String[]{"w", "x", "y", "z"});
        }};
        flashBack(0, digits, new StringBuilder(), strings, map);
        return strings;
        
    }
    
    private void flashBack(int index, String digits, StringBuilder prefix, List<String> stringList, Map<Character, String[]> map) {
        if (index == digits.length()) {
            stringList.add(prefix.toString());
        } else {
            String[] strings = map.get(digits.charAt(index));
            for (int i = 0; i < strings.length; ++i) {
                prefix = prefix.append(strings[i]);//1
                flashBack(index + 1, digits, prefix, stringList, map);
                prefix = prefix.deleteCharAt(index);//将上上行添加的字符移除进行下一次循环
            }
        }
    }
    
    
    public static void main(String[] args) {
        Solution17 solution17 = new Solution17();
        String digits = "23";
        System.out.println(solution17.letterCombinations2(digits));
    }
}