LeetCode-Solution/src/_017/Solution.java at master · RichCodersAndMe/LeetCode-Solution · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
package _017;

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * <pre>
 *     author: Blankj
 *     blog  : http://blankj.com
 *     time  : 2017/10/15
 *     desc  :
 * </pre>
 */
public class Solution {
//    private static String[] map = new String[]{"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
//
//    public List<String> letterCombinations(String digits) {
//        if (digits.length() == 0) return Collections.emptyList();
//        List<String> list = new ArrayList<>();
//        helper(list, digits, "");
//        return list;
//    }
//
//    private void helper(List<String> list, String digits, String ans) {
//        if (ans.length() == digits.length()) {
//            list.add(ans);
//            return;
//        }
//        for (char c : map[digits.charAt(ans.length()) - '2'].toCharArray()) {
//            helper(list, digits, ans + c);
//        }
//    }

    private static String[] map = new String[]{"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    public List<String> letterCombinations(String digits) {
        if (digits.length() == 0) return Collections.emptyList();
        LinkedList<String> list = new LinkedList<>();
        list.add("");
        char[] charArray = digits.toCharArray();
        for (int i = 0; i < charArray.length; i++) {
            char c = charArray[i];

            while (list.getFirst().length() == i) {
                String pop = list.removeFirst();
                for (char v : map[c - '2'].toCharArray()) {
                    list.addLast(pop + v);
                }
            }
        }
        return list;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.letterCombinations("23"));
    }
}