LeetCode-91-Decode Ways

题意

有一个消息包含A-Z通过以下规则编码:

现在给你一个加密过后的消息,问有几种解码的方式 ?如给出消息“12”,有两种解码的方法 AB(12) 或者 L(12),所以返回 2

思路

这道题其实和爬楼梯非常相似。我们知道爬楼梯的递推公式为:f(n) = f(n-1)+f(n-2)。这道题也有类似的公式,不过由于解码时输入需要在码表所规定的范围内,所以可能有f(n) = f(n-1)+f(n-2),可能有f(n) = f(n-1),还可能有f(n) = f(n-2),分别对应下面三种情况:

  • “XXX123″,这个字符串可以拆成”XXX1″和”23″,也可以拆成”XXX12″和”3″,因此f(n) = f(n-1)+f(n-2)
  • “XXX120″,这个字符串只能拆成”XXX1″和”20″,因此f(n) = f(n-2)
  • “XXX127″,这个字符串只能拆成”XXX12″和”7″,因此f(n) = f(n-1)

实现

由上述条件及相应的递推公式,实现如下:

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据