Letter Combinations of a Phone Number

1package pkg5leetcode.top100;2 3/*4 * Letter Combinations of a Phone Number | LC 175 * APPROACH: Backtrack building strings digit by digit.6 * COMPLEXITY: Time O(4^n), Space O(n)7 */8import java.util.*;9 10public class top100_LC17LetterCombinationsOfAPhoneNumber {11    static final String[] MAP = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};12 13    static List<String> letterCombinations(String digits) {14        List<String> res = new ArrayList<>();15        if (digits.isEmpty()) return res;16        backtrack(digits, 0, new StringBuilder(), res);17        return res;18    }19 20    static void backtrack(String d, int i, StringBuilder sb, List<String> res) {21        if (i == d.length()) { res.add(sb.toString()); return; }22        for (char c : MAP[d.charAt(i) - '0'].toCharArray()) {23            sb.append(c);24            backtrack(d, i + 1, sb, res);25            sb.deleteCharAt(sb.length() - 1);26        }27    }28 29    public static void main(String[] args) {30        check(letterCombinations("23").size() == 9, "case1");31        check(letterCombinations("").isEmpty(), "case2");32        System.out.println("all tests passed");33    }34 35    static void check(boolean cond, String name) {36        if (!cond) throw new AssertionError("FAILED: " + name);37        System.out.println("  PASS " + name);38    }39}