面试题库 › C++ / 后端 › 数字串解码方法数(1-26对应a-z,力扣91)

数字串解码方法数(1-26对应a-z,力扣91)

难度 ★★☆在 2 场真实面经中被问到 方向:C++ / 后端考点:动态规划

哪些公司问过

美团1亚马逊1

常见岗位:软件开发、C/C++ 软件开发

答案要点

  1. dp[i]表示前i个字符的解码数,初始dp[0]=1
  2. 当前字符在1-9时,dp[i]+=dp[i-1]
  3. 前两位组成10-26时,dp[i]+=dp[i-2]
  4. 处理0:不能单独解码,只能与前导1或2组成10、20,否则结果为0
  5. 滚动变量优化到O(1)空间,时间O(n)

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题