import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class _17 {
    static class Solution1 {
        public List<String> letterCombinations(String digits) {
            //map[x-2]; x ->[2,9];
            char[][] map = {
                    {'a', 'b', 'c'},
                    {'d', 'e', 'f'},
                    {'g', 'h', 'i'},
                    {'j', 'k', 'l'},
                    {'m', 'n', 'o'},
                    {'p', 'q', 'r', 's'},
                    {'t', 'u', 'v'},
                    {'w', 'x', 'y', 'z'}
            };
            List<String> res = new ArrayList<>();
            dfs(0, digits, new char[digits.length()], map, res);
            return res;
        }

        public void dfs(int i, String digits, char[] seen, char[][] map, List<String> res) {
            if (i >= digits.length()) {
                if (i > 0) res.add(String.valueOf(seen));
                return;
            }
            int val = digits.charAt(i) - '2';
            for (char ch : map[val]) {
                seen[i] = ch;
                dfs(i + 1, digits, seen, map, res);
            }
        }
    }

    static class Solution2 {
        public List<String> letterCombinations(String digits) {
            //队列
            char[][] map = {
                    {'a', 'b', 'c'},
                    {'d', 'e', 'f'},
                    {'g', 'h', 'i'},
                    {'j', 'k', 'l'},
                    {'m', 'n', 'o'},
                    {'p', 'q', 'r', 's'},
                    {'t', 'u', 'v'},
                    {'w', 'x', 'y', 'z'}
            };
            LinkedList<String> res = new LinkedList<>();
            if (digits.length() > 0) res.add("");
            for (int i = 0; i < digits.length(); i++) {
                int val = digits.charAt(i) - '2';
                while (res.peek().length() == i) {
                    String cur = res.poll();
                    for (char ch : map[val]) {
                        res.offer(cur + ch);
                    }
                }
            }
            return res;
        }
    }
}