LeetCode - Letter Combinations of a Phone Number

問題の説明

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

I/O例

Example 1:
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Example 2:
Input: digits = ""
Output: []

せいげんじょうけん

0 <= digits.length <= 4
digits[i] is a digit in the range ['2', '9'].

Solution

[戦略]
1.各ダイヤルボックスの可能な文字を管理する
2.2つのスタックを使用

以前にコンビネーションキャビネットのスタックを保存し、スタックからスタックを取り出し、コンビネーションスタック

を保存するために文字を追加する.

class Solution {
    public List<String> letterCombinations(String digits) {

        char[][] dials = { { '-', '-', '-', '-' }, { '-', '-', '-', '-' }, { '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' } };

        if (digits.length() < 1) {
            return new ArrayList<>();
        }

        Stack<StringBuilder> dialCombinations = new Stack<>();
        Stack<StringBuilder> conveyStacks = new Stack<>();

        dialCombinations.add(new StringBuilder());
        // boolean[] visits = new boolean[digits.length()];
        for (int i = 0; i < digits.length(); i++) {
            int number = digits.charAt(i) - 48;
            while (!dialCombinations.empty()) {
                StringBuilder popSb = dialCombinations.pop();
                for (int j = 0; j < dials[0].length; j++) {
                    if (dials[number][j] == '-') {
                        break;
                    }
                    StringBuilder newSb = new StringBuilder(popSb);
                    newSb.append(dials[number][j]);
                    conveyStacks.push(newSb);
                }
            }
            dialCombinations = conveyStacks;
            conveyStacks.clear();
        }

        ArrayList<String> resultDigitsComb = new ArrayList<>();

        for (StringBuilder sb : dialCombinations) {
            resultDigitsComb.add(sb.toString());
        }

        return resultDigitsComb;
    }
}