Problem of The Day: Letter Combinations of a Phone Number

Problem Statement

leetcode problem link

My Solution [Accepted]

public class Solution {
    public Dictionary<char, string> NumToLetters => new Dictionary<char, string> {
        { '2', "abc" },
        { '3', "def" },
        { '4', "ghi" },
        { '5', "jkl" },
        { '6', "mno" },
        { '7', "pqrs" },
        { '8', "tuv" },
        { '9', "wxyz" },
        { '0', "" },
        { '1', "" }
    };

    public IList<string> res { get; set;} = new List<string>();

    public void BackTrack (int start, string digits, List<string> curr) {
        if (start == digits.Length) {
            res.Add(string.Join("", curr));
            return;
        }
        foreach (var ch in NumToLetters[digits[start]]) {
            curr.Add(ch.ToString());
            int lastIdx = curr.Count - 1;
            BackTrack(start + 1, digits, curr);
            curr.RemoveAt(lastIdx);
        }

    }

    public IList<string> LetterCombinations(string digits) {
        BackTrack(0, digits, new List<string>());
        return res;
    }
}

Editorial

Approach 1: Backtracking

public class Solution {
    private List<string> combinations = new List<string>();

    private Dictionary<char, string> letters = new Dictionary<char, string> {
        { '2', "abc" }, { '3', "def" },  { '4', "ghi" }, { '5', "jkl" },
        { '6', "mno" }, { '7', "pqrs" }, { '8', "tuv" }, { '9', "wxyz" }
    };

    private string phoneDigits;

    public IList<string> LetterCombinations(string digits) {
        if (digits.Length == 0) {
            return combinations;
        }

        phoneDigits = digits;
        Backtrack(0, new StringBuilder());
        return combinations;
    }

    private void Backtrack(int index, StringBuilder path) {
        if (path.Length == phoneDigits.Length) {
            combinations.Add(path.ToString());
            return;
        }

        string possibleLetters = letters[phoneDigits[index]];
        foreach (char letter in possibleLetters) {
            path.Append(letter);
            Backtrack(index + 1, path);
            path.Remove(path.Length - 1, 1);
        }
    }
}

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        # If the input is empty, immediately return an empty answer array
        if len(digits) == 0:
            return []

        # Map all the digits to their corresponding letters
        letters = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
        }

        def backtrack(index, path):
            # If the path is the same length as digits, we have a complete combination
            if len(path) == len(digits):
                combinations.append("".join(path))
                return  # Backtrack

            # Get the letters that the current digit maps to, and loop through them
            possible_letters = letters[digits[index]]
            for letter in possible_letters:
                # Add the letter to our current path
                path.append(letter)
                # Move on to the next digit
                backtrack(index + 1, path)
                # Backtrack by removing the letter before moving onto the next
                path.pop()

        # Initiate backtracking with an empty path and starting index of 0
        combinations = []
        backtrack(0, [])
        return combinations