17. Letter Combinations of a Phone Number

https://leetcode.com/problems/letter-combinations-of-a-phone-number/

Python

• Time: O(4^N)

7 and 9 has 4 characters

• Space: O(1)

class Solution:
    MAP = {
        '2': 'abc',
        '3': 'def',
        '4': 'ghi',
        '5': 'jkl',
        '6': 'mno',
        '7': 'pqrs',
        '8': 'tuv',
        '9': 'wxyz',
    }

    def letterCombinations(self, digits: str) -> List[str]:
        result = []

        if not digits:
            return result

        def backtrack(word, i):
            if len(word) == len(digits):
                result.append(word)
                return

            for char in self.MAP[digits[i]]:
                backtrack(word+char, i+1)

        backtrack('', 0)

        return result

Javascript

const phones = {
	2: "abc",
	3: "def",
	4: "ghi",
	5: "jkl",
	6: "mno",
	7: "pqrs",
	8: "tuv",
	9: "wxyz",
};

var letterCombinations = function (digits) {
  if (!digits.length) return [];
	const result = [];

	var backtrack = function (start, digits, record = []) {
		if (record.length === digits.length) {
			result.push(record.join(""));
			return;
		}

		for (let char of phones[digits[start]]) {
			record.push(char);
			backtrack(start + 1, digits, record);
			record.pop();
		}
	};
	backtrack(0, digits);

	return result;
};