Leetcode | Letter Combinations of a Phone Number | Java

devstromo · devstromo · commit f62d18bc3944 · 2025-05-09T21:41:33.000-03:00
diff --git a/leetcode/src/main/java/com/devstromo/medium/p17/DESCRIPTION.md b/leetcode/src/main/java/com/devstromo/medium/p17/DESCRIPTION.md
@@ -0,0 +1,27 @@
+# 17. Letter Combinations of a Phone Number
+
+Given a string containing digits from `2-9` inclusive, return all possible letter combinations that the number could
+represent. Return the answer in any order.
+
+A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any
+letters.
+
+Example 1:
+
+Input: digits = "23"
+Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
+
+Example 2:
+
+Input: digits = ""
+Output: []
+
+Example 3:
+
+Input: digits = "2"
+Output: ["a","b","c"]
+
+Constraints:
+
+- `0 <= digits.length <= 4`
+- `digits[i]` is a digit in the range `['2', '9']`.
diff --git a/leetcode/src/main/java/com/devstromo/medium/p17/Solution.java b/leetcode/src/main/java/com/devstromo/medium/p17/Solution.java
@@ -0,0 +1,34 @@
+package com.devstromo.medium.p17;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Map;
+
+public class Solution {
+    private static final Map<Character, String> phoneMap = Map.of(
+            '2', "abc", '3', "def",
+            '4', "ghi", '5', "jkl", '6', "mno",
+            '7', "pqrs", '8', "tuv", '9', "wxyz"
+    );
+
+    public List<String> letterCombinations(String digits) {
+        List<String> result = new ArrayList<>();
+        if (digits == null || digits.isEmpty()) return result;
+        backtrack(digits, 0, new StringBuilder(), result);
+        return result;
+    }
+
+    private void backtrack(String digits, int index, StringBuilder path, List<String> result) {
+        if (index == digits.length()) {
+            result.add(path.toString());
+            return;
+        }
+
+        String possibleLetters = phoneMap.get(digits.charAt(index));
+        for (char c : possibleLetters.toCharArray()) {
+            path.append(c);
+            backtrack(digits, index + 1, path, result);
+            path.deleteCharAt(path.length() - 1); // backtrack
+        }
+    }
+}
diff --git a/leetcode/src/test/java/com/devstromo/medium/p17/SolutionUnitTest.java b/leetcode/src/test/java/com/devstromo/medium/p17/SolutionUnitTest.java
@@ -0,0 +1,21 @@
+package com.devstromo.medium.p17;
+
+import org.junit.jupiter.api.DisplayName;
+import org.junit.jupiter.api.Test;
+
+import java.util.List;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+class SolutionUnitTest {
+    private final Solution solution = new Solution();
+
+    @Test
+    @DisplayName("Letter Combinations of a Phone Number")
+    void letterCombinations() {
+        assertEquals(List.of("ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"), solution.letterCombinations("23"));
+        assertEquals(List.of(), solution.letterCombinations(""));
+        assertEquals(List.of("a", "b", "c"), solution.letterCombinations("2"));
+    }
+
+}
