Blind 75
Decode Ways
- Problem
- LC 91
- Category
- DP
- File
- blind75_LC91DecodeWays.java
- Path
- pkg5leetcode/blind75/blind75_LC91DecodeWays.java
- Package
- pkg5leetcode.blind75
- Command
- java pkg5leetcode/blind75/blind75_LC91DecodeWays.java
- Approach
- DP count ways to decode prefix; handle '0' invalid splits.
- Complexity
- Time O(n), Space O(n)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.blind75;2 3/*4 * Decode Ways | LC 915 * APPROACH: DP count ways to decode prefix; handle '0' invalid splits.6 * COMPLEXITY: Time O(n), Space O(n)7 */8public class blind75_LC91DecodeWays {9 static int numDecodings(String s) {10 if (s.charAt(0) == '0') return 0;11 int n = s.length();12 int[] dp = new int[n + 1];13 dp[0] = 1;14 dp[1] = 1;15 for (int i = 2; i <= n; i++) {16 if (s.charAt(i - 1) != '0') dp[i] += dp[i - 1];17 int two = Integer.parseInt(s.substring(i - 2, i));18 if (two >= 10 && two <= 26) dp[i] += dp[i - 2];19 }20 return dp[n];21 }22 23 public static void main(String[] args) {24 check(numDecodings("12") == 2, "case1");25 check(numDecodings("226") == 3, "case2");26 System.out.println("all tests passed");27 }28 29 static void check(boolean cond, String name) {30 if (!cond) throw new AssertionError("FAILED: " + name);31 System.out.println(" PASS " + name);32 }33}