描述

有一种将字母编码成数字的方式:'a'->1, 'b->2', ... , 'z->26'。

我们把一个字符串编码成一串数字,再考虑逆向编译成字符串。

由于没有分隔符,数字编码成字母可能有多种编译结果,例如 11 既可以看做是两个 'a' 也可以看做是一个 'k' 。但 10 只可能是 'j' ,因为 0 不能编译成任何结果。

现在给一串数字,返回有多少种可能的译码结果

状态方程:f(i)=f(i−1)+f(i−2)
边界条件是 f(-1) = 0,f(0) = 1。
优化: f(i) 只和它的前两项 f(i−1) 和 f(i−2) 相关,可以运用「滚动数组」思想把 f 数组压缩成三个变量,这样空间复杂度就变成了 O(1)。虽然这里用了滚动数组,动态规划部分的空间代价是 O(1) 的,但是这里用了一个临时变量把数字转化成了字符串,故渐进空间复杂度也是 O(logn)。

class Solution {
public:
    /**
     * 解码
     * @param nums string字符串 数字串
     * @return int整型
     */
    int solve(string nums) {
        // write code here
        int n = nums.length();
		if (n <= 0)
			return 0;
		int leftleft = 0, left = 1, res = 1;//leftleft表示第i-2位,left表示第i-1位,res表示以第i位结尾时的个数
		for (int i = 1; i < n; ++i)
		{
			leftleft = left;
			left = res;
			if (nums[i] == '0')//如果当前位是0那么就不能再加f(i−1)
				res = 0;//f(i)=0
			else
				res = left;//默认是它前一位的数量f(i)=f(i−1)
			auto pre = nums.substr(i-1, 2);//当前这一位和它前面一位组成二位数			
			if (pre <= "26"&&pre >= "10")
				res += leftleft;//f(i)=f(i−1)+f(i−2)
			
		}
		return res;
    }
};