Leetcode interview preparation: Decode Ways

1 topic

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1'B' -> 2... 'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,

Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

public int numDecodings(String s);

2 thoughts

One-dimensional dynamic programming, lazy, copy the blog post.

Analysis: It should be noted that if there is a 0 in the sequence that cannot be matched, then the decoding method is 0, such as the sequence 012, 100 (the second 0 can be combined with 1 to form 10, and the third 0 cannot match).

Recursive solutions are easy, but large collections can time out. Converting to dynamic programming, assume dp[i] denotes the sequence s[0... i-1]

The dynamic programming equation is as follows:

Initial conditions: dp[0] = 1, dp[1] = (s[0] == '0')? 0 : 1

dp[i] = ( s[i-1] == 0 ? 0 : dp[i-1] ) + ( s[i-2,i-1] can represent letters? dp[i-2] : 0 ), where the first component is to put s[0... Consider the last digit of i-1 as a letter, and the second component is s[0... Consider the last two digits of i-1 as a single letter

Complexity: O(n); Space O(n)

3 code public int numDecodings(String s) { // 1. Initialize final int len = s.length(); if (len == 0) return 0; int[] dp = new int[len + 1]; dp[0] = 1; if (s.charAt(0) != '0') dp[1] = 1; else dp[1] = 0; // 2. One-dimensional DP equation for (int i = 2; i