Leetcode | Decode Ways | Java

devstromo · devstromo · commit 4b7bc87b88cd · 2025-05-02T23:33:33.000-03:00
diff --git a/leetcode/src/main/java/com/devstromo/medium/p91/DESCRIPTION.md b/leetcode/src/main/java/com/devstromo/medium/p91/DESCRIPTION.md
@@ -0,0 +1,65 @@
+# 91. Decode Ways
+
+You have intercepted a secret message encoded as a string of numbers. The message is decoded via the following mapping:
+
+`"1" -> 'A'`
+
+`"2" -> 'B'`
+
+`...`
+
+`"25" -> 'Y'`
+
+`"26" -> 'Z'`
+
+However, while decoding the message, you realize that there are many different ways you can decode the message because some codes are contained in other codes (`"2"` and `"5"` vs `"25"`).
+
+For example, `"11106"` can be decoded into:
+
+- `"AAJF"` with the grouping `(1, 1, 10, 6)`
+- `"KJF"` with the grouping `(11, 10, 6)`
+- The grouping `(1, 11, 06)` is invalid because `"06"` is not a valid code (only `"6"` is valid).
+
+Note: there may be strings that are impossible to decode.
+
+Given a string s containing only digits, return the number of ways to decode it. If the entire string cannot be decoded
+in any valid way, return 0.
+
+The test cases are generated so that the answer fits in a 32-bit integer.
+
+Example 1:
+
+Input: s = "12"
+
+Output: 2
+
+Explanation:
+
+"12" could be decoded as "AB" (1 2) or "L" (12).
+
+Example 2:
+
+Input: s = "226"
+
+Output: 3
+
+Explanation:
+
+"226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
+
+Example 3:
+
+Input: s = "06"
+
+Output: 0
+
+Explanation:
+
+"06" cannot be mapped to "F" because of the leading zero ("6" is different from "06"). In this case, the string is not a
+valid encoding, so return 0.
+
+Constraints:
+
+- `1 <= s.length <= 100`
+- `s` contains only digits and may contain leading zero(s).
+
diff --git a/leetcode/src/main/java/com/devstromo/medium/p91/Solution.java b/leetcode/src/main/java/com/devstromo/medium/p91/Solution.java
@@ -0,0 +1,30 @@
+package com.devstromo.medium.p91;
+
+import java.util.Arrays;
+
+public class Solution {
+    public int numDecodings(String s) {
+        int n = s.length();
+        int[] dp = new int[n];
+        Arrays.fill(dp, -1);
+        return dfs(0, s, dp);
+    }
+
+    private int dfs(int index, String s, int[] dp) {
+        if (index == s.length()) return 1; // Reached end: 1 valid decoding path
+        if (s.charAt(index) == '0') return 0; // '0' can't start a valid code
+        if (dp[index] != -1) return dp[index];
+
+        int result = dfs(index + 1, s, dp);
+
+        if (index + 1 < s.length()) {
+            int num = Integer.parseInt(s.substring(index, index + 2));
+            if (num >= 10 && num <= 26) {
+                result += dfs(index + 2, s, dp);
+            }
+        }
+
+        dp[index] = result;
+        return result;
+    }
+}
diff --git a/leetcode/src/test/java/com/devstromo/medium/p91/SolutionUnitTest.java b/leetcode/src/test/java/com/devstromo/medium/p91/SolutionUnitTest.java
@@ -0,0 +1,19 @@
+package com.devstromo.medium.p91;
+
+import org.junit.jupiter.api.DisplayName;
+import org.junit.jupiter.api.Test;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+class SolutionUnitTest {
+    private final Solution solution = new Solution();
+
+    @Test
+    @DisplayName("Test Decode Ways")
+    void testDecodeWays() {
+        assertEquals(2, solution.numDecodings("12"));
+        assertEquals(3, solution.numDecodings("226"));
+        assertEquals(0, solution.numDecodings("06"));
+    }
+
+}
