How does dynamic programming apply to the Decode Ways problem?

Dynamic programming is used to efficiently count the number of ways a string can be decoded by storing intermediate results in a dp array. This avoids recalculating the number of decodings for overlapping subproblems.

What is the time complexity of the Decode Ways problem?

The time complexity of this problem is O(n), where n is the length of the input string. The solution iterates over the string once, processing each character in constant time.

Can the Decode Ways problem have invalid strings?

Yes, a string with leading zeros or values outside the range of 1 to 26 cannot be decoded. These cases should be handled explicitly by returning 0 for invalid input.

What is the base case for dynamic programming in Decode Ways?

The base case for dynamic programming is dp[0] = 1, representing the number of ways to decode the empty string. dp[1] is 1 if the first character is not '0'.

Are there any alternate approaches to solve the Decode Ways problem?

Yes, instead of dynamic programming, recursion with memoization could also be used to solve the problem, though it might not be as efficient in terms of space.

#91

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

解码方法

一条包含字母 A-Z 的消息通过以下映射进行了编码： "1" -> 'A' "2" -> 'B' ... "25" -> 'Y' "26" -> 'Z' 然而，在解码已编码的消息时，你意识到有许多不同的方式来解码，因为有些编码被包含在其它编码当中（ "2" 和 "5" 与 "25" ）。例…

字符串动态规划

题目描述

一条包含字母 A-Z 的消息通过以下映射进行了编码：

"1" -> 'A' "2" -> 'B' ... "25" -> 'Y' "26" -> 'Z'

然而，在解码已编码的消息时，你意识到有许多不同的方式来解码，因为有些编码被包含在其它编码当中（"2" 和 "5" 与 "25"）。

例如，"11106" 可以映射为：

"AAJF" ，将消息分组为 (1, 1, 10, 6)
"KJF" ，将消息分组为 (11, 10, 6)
消息不能分组为 (1, 11, 06) ，因为 "06" 不是一个合法编码（只有 "6" 是合法的）。

注意，可能存在无法解码的字符串。

给你一个只含数字的非空字符串 s ，请计算并返回解码方法的总数。如果没有合法的方式解码整个字符串，返回 0。

题目数据保证答案肯定是一个 32 位 的整数。

示例 1：

输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。

示例 2：

输入：s = "226"
输出：3
解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

示例 3：

输入：s = "06"
输出：0
解释："06" 无法映射到 "F" ，因为存在前导零（"6" 和 "06" 并不等价）。

提示：

1 <= s.length <= 100
s 只包含数字，并且可能包含前导零。

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i]$ 表示字符串的前 $i$ 个字符的解码方法数，初始时 $f[0]=1$ ，其余 $f[i]=0$ 。

考虑 $f[i]$ 如何进行状态转移。

如果第 $i$ 个字符（即 $s[i-1]$ ）单独形成编码，那么它对应一种解码方式，即 $f[i]=f[i-1]$ 。前提是 $s[i-1] \neq 0$ 。
如果第 $i-1$ 个字符和第 $i$ 个字符组成的字符串在 $[1,26]$ 范围内，那么它们可以作为一个整体，对应一种解码方式，即 $f[i] = f[i] + f[i-2]$ 。前提是 $s[i-2] \neq 0$ ，且 $s[i-2]s[i-1]$ 在 $[1,26]$ 范围内。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是字符串的长度。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        f = [1] + [0] * n
        for i, c in enumerate(s, 1):
            if c != "0":
                f[i] = f[i - 1]
            if i > 1 and s[i - 2] != "0" and int(s[i - 2 : i]) <= 26:
                f[i] += f[i - 2]
        return f[n]

我们注意到，状态 $f[i]$ 仅与状态 $f[i-1]$ 和状态 $f[i-2]$ 有关，而与其他状态无关，因此我们可以使用两个变量代替这两个状态，使得原来的空间复杂度 $O(n)$ 降低至 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def numDecodings(self, s: str) -> int:
        f, g = 0, 1
        for i, c in enumerate(s, 1):
            h = g if c != "0" else 0
            if i > 1 and s[i - 2] != "0" and int(s[i - 2 : i]) <= 26:
                h += f
            f, g = g, h
        return g

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate identify the base cases for dynamic programming?
question_mark
Do they account for edge cases like leading zeros or invalid two-digit numbers?
question_mark
Can the candidate explain how state transitions work in dynamic programming for this problem?

warning

常见陷阱

外企场景

error
Forgetting to initialize the dp array correctly, especially handling dp[1] when s[0] is '0'.
error
Not checking if a two-digit number is valid before adding to dp[i].
error
Misunderstanding the significance of leading zeros and not handling them properly.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Considerations for decoding strings with additional constraints like very large numbers.
arrow_right_alt
Alternative approaches using recursion with memoization instead of dynamic programming.
arrow_right_alt
Variation where instead of decoding to letters, the numbers correspond to a different set of symbols or characters.

help

常见问题

外企场景

继续练习

#87 扰乱字符串 #97 交错字符串 #72 编辑距离