LeetCOde-剑指46-把数字翻译成字符串

1、动态规划法

我们通过观察可以发现，假如我们使用数组$dp[i]$来记录前$i$位可能构成的字符串个数：1、当新加入的第$i+1$位和第$i$位能够构成一个大于9小于26的数字时，$dp[i+1]=dp[i]+dp[i-1]$；2、当不能构成这样的一个数字时，$dp[i+1]=dp[i]$。由于我们一共只使用到两个变量，因此我们可以直接使用两个int类型变量来代替数组。

class Solution {
public:
    int translateNum(int num) {
        string s = to_string(num);
        int temp_num = 1, temp_add = 1, temp;
        for (int i = 1; i < s.size(); ++i) {
            temp = temp_num;
            int temp_i = stoi(s.substr(i - 1, 2));
            if (temp_i < 26 && temp_i > 9) {
                temp_num += temp_add;
            }
            temp_add = temp;
        }
        return temp_num;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

或

class Solution {
public:
    int translateNum(int num) {
        string src = to_string(num);
        int p = 0, q = 0, r = 1;
        for (int i = 0; i < src.size(); ++i) {
            p = q; 
            q = r; 
            r = 0;
            r += q;
            if (i == 0) {
                continue;
            }
            auto pre = src.substr(i - 1, 2);
            if (pre <= "25" && pre >= "10") {
                r += p;
            }
        }
        return r;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

其中还方法二为滚动数组优化。