91.解码方法.md

91.解码方法

/*
 * @lc app=leetcode.cn id=91 lang=typescript
 *
 * [91] 解码方法
 */

// @lc code=start
function numDecodings(s: string): number {}
// @lc code=end

解法 1: 动态规划

• 时间复杂度:
• 空间复杂度:

1. 子问题: 第 i 个字符时,能组成的解码总数
2. 状态:
   • dp[i]: s[0~i] 所能组成的解码总数
3. DP 方程:
   • dp[i] = (s[i]!==0?dp[i-1]:0) + (s[i-1]!==0&&s[i-1]+s[i]<=26?dp[i-2]:0)

• 最后一位单独解码
  • 最后一位不能为 0
  • 解码方法总数为 dp[i-1]
• 最后两位一块解码
  • 倒数第二位不能为 0
  • 解码方法总数为 dp[i-2]

function numDecodings(s: string): number {
  const dp: number[] = []
  for (let i = 0; i < s.length; i++) {
    dp[i] =
      (s[i] !== '0' ? dp[i - 1] ?? 1 : 0) + (s[i - 1] !== '0' && parseInt(s[i - 1] + s[i]) <= 26 ? dp[i - 2] ?? 1 : 0)
  }

  return dp[s.length - 1]
}

Case

test.each([
  { input: { s: '12' }, output: 2 },
  { input: { s: '226' }, output: 3 },
  { input: { s: '0' }, output: 0 },
  { input: { s: '06' }, output: 0 },
  { input: { s: '11106' }, output: 2 },
])(`input: s = $input.s`, ({ input: { s }, output }) => {
  expect(numDecodings(s)).toBe(output)
})