feat(solution): Added solution for 0017

maxchui · maxchui · commit 523c554f46e2 · 2024-05-31T22:16:35.000-04:00
diff --git a/0001-1000.md b/0001-1000.md
@@ -3,6 +3,7 @@
 ## Algorithms <!-- omit from toc -->
 
 - [Array](#array)
+- [Backtracking](#backtracking)
 - [Binary Search](#binary-search)
 - [Dynamic Programming](#dynamic-programming)
 - [Greedy](#greedy)
@@ -16,6 +17,12 @@
 |-----|---------------- | --------------- | --------------- | --------------- | ------------- |--------------|-----|
 |1672|[Richest Customer Wealth](https://leetcode.com/problems/richest-customer-wealth/)| [C#](./C%23/1672-Richest_Customer_Wealth.cs)| $O(n \cdot m)$| $O(1)$|Easy|||
 
+## Backtracking
+
+|  #  | Title           |  Solution       |  Time           | Space           | Difficulty    | Tag          | Note|  
+|-----|---------------- | --------------- | --------------- | --------------- | ------------- |--------------|-----|
+|0017|[Letter Combinations of a Phone Number](https://leetcode.com/problems/letter-combinations-of-a-phone-number/)| [C#](./C%23/0017-Letter_Combinations_of_a_Phone_Number.cs)| $O(4^n)$| $O(4^n)$|Medium|||
+
 ## Binary Search
 
 |  #  | Title           |  Solution       |  Time           | Space           | Difficulty    | Tag          | Note|  
diff --git a/C#/0017-Letter_Combinations_Of_A_Phone_Number.cs b/C#/0017-Letter_Combinations_Of_A_Phone_Number.cs
@@ -0,0 +1,44 @@
+// URL: https://leetcode.com/problems/letter-combinations-of-a-phone-number/
+// Time Complexity: O(4^n)
+// Space Complexity: O(4^n)
+
+public class Solution
+{
+    public IList<string> LetterCombinations(string digits)
+    {
+        if (string.IsNullOrEmpty(digits)) return [];
+
+        Dictionary<string, string> map = new Dictionary<string, string>(){
+            {"2", "abc"},
+            {"3", "def"},
+            {"4", "ghi"},
+            {"5", "jkl"},
+            {"6", "mno"},
+            {"7", "qprs"},
+            {"8", "tuv"},
+            {"9", "wxyz"}
+        };
+
+        IList<string> combinations = new List<string>();
+
+        void Backtracking(int index, string current)
+        {
+            if (current.Length == digits.Length)
+            {
+                combinations.Add(current);
+                return;
+            }
+
+            string chars = map[digits[index].ToString()];
+
+            for (int i = 0; i < chars.Length; i++)
+            {
+                Backtracking(index + 1, current + chars[i]);
+            }
+        }
+
+        Backtracking(0, "");
+
+        return combinations;
+    }
+}
