Letter Combinations of a Phone Number

1package pkg5leetcode.official75;2 3/*4 * Letter Combinations of a Phone Number | LC 175 * APPROACH: Backtracking map digits to letters.6 * COMPLEXITY: Time O(4^n), Space O(n)7 */8import java.util.*;9 10public class official75_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 digits, int i, StringBuilder path, List<String> res) {21        if (i == digits.length()) { res.add(path.toString()); return; }22        for (char c : MAP[digits.charAt(i) - '0'].toCharArray()) {23            path.append(c);24            backtrack(digits, i + 1, path, res);25            path.deleteCharAt(path.length() - 1);26        }27    }28 29    public static void main(String[] args) {30        List<String> r = letterCombinations("23");31        check(r.size() == 9 && r.contains("ad") && r.contains("cf"), "case1");32        check(letterCombinations("").isEmpty(), "case2");33        System.out.println("all tests passed");34    }35 36    static void check(boolean cond, String name) {37        if (!cond) throw new AssertionError("FAILED: " + name);38        System.out.println("  PASS " + name);39    }40}