Ways to Decode

Logical Breakdown

• [ ] Subproblem Identification:
• [ ] Optimal Substructure:
• [ ] Constraint Handling: (e.g., Modulo \(10^9 + 7\))
• [ ] Optimization: (Matrix Exponentiation if 'A' is huge)

---

Mathematical Rigor

State Definition

Let \(dp[i]\) be the state for the \(i\)-th subproblem.

Recurrence Relation

\[ dp[i] = ... \]

---

Visualization

graph TD A["Current State"] --> B["Previous State 1"] A --> C["Previous State 2"]

---

Complexity Analysis

Approach	Time Complexity	Space Complexity
Iterative DP	\(O(N)\)	\(O(1)\)

---

Code Reference

package com.dsa.dynamic_programming;

import java.util.*;

/ * Problem: Ways to Decode * Group: 11. Dynamic Programming */ / * ============================================================================================ * PROBLEM: Ways to Decode (Decode Ways) * ============================================================================================ * * --------------------- * 1. Problem Description * --------------------- * A message containing letters from A-Z is being encoded to numbers using the mapping: * 'A' -> 1, 'B' -> 2 ... 'Z' -> 26. * Given a numeric string A, determine the total number of ways to decode it. * * Example: "12" -> "AB" (1, 2) or "L" (12). Total 2 ways. * * --------------------- * 2. Logical Breakdown & Mathematical Formulation * --------------------- * Let dp[i] be the number of ways to decode the prefix A[0...i-1] (length i). * * To calculate dp[i], we look back at the last 1 or 2 digits ending at i-1: * * 1. Single Digit Decode (A[i-1]): * - If A[i-1] is '1'-'9' (not '0'), we can treat it as a single letter. * - Contribution: + dp[i-1] * * 2. Double Digit Decode (A[i-2] and A[i-1]): * - If the substring A[i-2...i-1] forms a number between 10 and 26, it corresponds to a valid letter. * - Contribution: + dp[i-2] * * Edge Case: * - '0' cannot stand alone. It must be paired with '1' or '2' (10 or 20). * - If a string starts with '0', ways = 0. * * Recurrence Relation: * dp[i] = (valid_single ? dp[i-1] : 0) + (valid_double ? dp[i-2] : 0) * * Base Cases: * dp[0] = 1 (Empty string has 1 way - do nothing). * dp[1] = 1 (If A[0] != '0'). * * --------------------- * 3. Constraints & Complexity Analysis * --------------------- * Constraints: * 1 <= |A| <= 10^5 * * Time Complexity: * O(N) - Single pass through the string. * * Space Complexity: * O(N) or O(1) if optimized (only need previous two states). * * ============================================================================================ */ public class WaysToDecode { public int solve(int A) { // TODO: Implement solution return 0; }

public int numDecodings(String number) {
    return 0;
}

}