[数据结构与算法]LeetCode 17（C#）

题目

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：
输入：digits = “23”
输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]

示例 2：
输入：digits = “”
输出：[]

示例 3：
输入：digits = “2”
输出：[“a”,“b”,“c”]

代码

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

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

        List<string> list = new List<string>();
        
        Dfs(list, digits, 0, new char[digits.Length]);

        return list;
    }

    private void Dfs(List<string> list, string digits, int index, char[] str)
    {
        if (index == digits.Length)
        {
            list.Add(new string(str));
            return;
        }

        foreach (var item in m_Dictionary[digits[index]])
        {
            str[index] = item;
            Dfs(list, digits, index + 1, str);
        }
    }
}