17. Letter Combinations of a Phone Number

class Solution {
    private static final String[] NUMBER_OFFSET_TO_LETTERS_MAP = new String[8];

    static {
        NUMBER_OFFSET_TO_LETTERS_MAP[0] = "abc";
        NUMBER_OFFSET_TO_LETTERS_MAP[1] = "def";
        NUMBER_OFFSET_TO_LETTERS_MAP[2] = "ghi";
        NUMBER_OFFSET_TO_LETTERS_MAP[3] = "jkl";
        NUMBER_OFFSET_TO_LETTERS_MAP[4] = "mno";
        NUMBER_OFFSET_TO_LETTERS_MAP[5] = "pqrs";
        NUMBER_OFFSET_TO_LETTERS_MAP[6] = "tuv";
        NUMBER_OFFSET_TO_LETTERS_MAP[7] = "wxyz";
    }

    public List<String> letterCombinations(String digits) {
        if (digits.isEmpty()) {
            return Collections.emptyList();
        }

        List<String> resultList = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        backtrack(resultList, sb, digits, 0);
        return resultList;
    }

    private void backtrack(List<String> resultList, StringBuilder sb, String digits, int i) {
        if (i == digits.length()) {
            resultList.add(sb.toString());
            return;
        }

        // 注意每个数字是必须要进行转换的，所以此处不能使用 for 循环，因为 for 循环具有不选元素的语义
        char number = digits.charAt(i);
        String letters = NUMBER_OFFSET_TO_LETTERS_MAP[number - '2'];
        for (int j = 0; j < letters.length(); j++) {
            sb.append(letters.charAt(j));
            backtrack(resultList, sb, digits, i + 1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

References

17. Letter Combinations of a Phone Number