一道笔试题： 输入一串数字，求对应英文字母出现的可能性 z = {'a':1, 'b':2, .... , 'z':26}, 输入： 123，输出： abc, lc, aw（l： 12， w： 23）

[xiaoming1992]

func
const result = []
const availTuples = [...]
availTuples.foreach
const (a, b) = tuple
result.push(map(a), func(b))
return result

[xiaoming1992]

艹了，我的空格缩进都给我吃掉了。。。

[lihongming]

第一反应是迭代。
每次截取 1-2 位数字（ 2 位数字需要<=26 ），然后把剩下的数字迭代给自己。

时间、空间复杂度都是 O(N)，准确来说是 2N，可能效率不是最高，但很容易想

[geelaw]

@lihongming #3 这个问题的输出长度可以达到 Omega(1.6^n)，因此不可能时间是 O(n)。

此外这个输出长度也表示空间至少需要 Omega(n)，因此朴素的算法已经是最佳。

[Mirage09]

https://leetcode.com/problems/decode-ways/

[lihongming]

@Mirage09 哈哈哈，第一次见这么多负分的题，竟然还有公司拿来笔试？

[lihongming]

@geelaw 是的，我想简单了，迭代的时间复杂度应该是 O(N^2)

[Mirage09]

@lihongming
downvote 多的题多了去了，比如这几个：
https://leetcode.com/problems/string-to-integer-atoi/
https://leetcode.com/problems/divide-two-integers/

[mskf]

刚试了下，反向 dp 应该是最简单的。。。不是很理解为啥这题这么多踩啊，是不是以前的测试数据有问题

[xiadong1994]

最基本的 dp

[caixiangyu17]

动态规划，根据第一位数值，分解成两个子问题
char(a[0])+f(a[1...n])
char(a[0]*10+a[1]) + f(a[2...n])
细节就不说了，会动态规划不难

[siriussilen]

这道题，可以从记忆化递归的角度来理解，比如对于一个字符串 F("2213")=5, 可以分解为 F("213")和 F("13")两个子问题，在 F("213")这个子问题中又可以分为 F("13")和 F("3")两个子子问题，F("13")这个子子问题和 F("13")子问题是重复的，因而可以考虑使用记忆化搜索或动态规划来解决这个问题。

特别地，如果一个数中的一个前缀和两个前缀都是合法的，那么这个值等于斐波那契数列+1(此时解空间实际上就等价于斐波那契数列的状态转移方式)，例如，f("12121212")=Fibonacci number(8+1) = 34

```cpp
class Solution {
public:
int numDecodings(string s) {
if(s.length() == 0) return 0;
unordered_map<string, int> ways;
ways[""] = 1;
function<int(const string &s)> dfs = [&](const string& s){
if(ways.count(s)) return ways[s];
if(s[0] == '0') return 0; // 第一位是 0，这是非法的返回 0
if(s.length() == 1) return 1; // e.g. 1-9,返回一种方式
int w = dfs(s.substr(1)); // 把第一位去掉，子问题 1
int prefix = stoi(s.substr(0,2)); // 取前两位，子问题 2
if(prefix <= 26) w += dfs(s.substr(2)); // 检查是否合法
ways[s] = w;
return w;
};
return dfs(s);
}
};
```

执行用时 :8 ms, 在所有 cpp 提交中击败了 37.55%的用户
内存消耗 :16.5 MB, 在所有 cpp 提交中击败了 5.18%的用户


记忆化搜索比较好理解，此外我的思考难免存在不足，欢迎批评指教

[knva]

首先分割这些字符
0 位为 0 直接返回 0 ；
若 s[i-1]==1 则 +1
若 s[i-1]==2 并且 s[i]<=6 +1

字符串中有 0 则特殊处理

[petelin]

这难道不是回溯吗

[zpfhbyx]

- -,这么多高大上,只有我是 kv 交换,然后输出 123 的排列组合中单个小于 26 的组合么..

[petelin]

```
func numDecodings(s string) (ans int) {
backtrace(s, &ans)
return
}

func backtrace(s string, ans *int){
if len(s) == 0{
*ans++
return
}
if '1' <= s[0] && s[0] <= '9'{
backtrace(s[1:], ans)
}

if len(s) > 1{
if (s[0] == '1') || (s[0] == '2' && '0' <= s[1] && s[1] <= '6') {
backtrace(s[2:], ans)
}
}
}```

这个叫不叫回溯? 有没有学院派大佬

[petelin]

我理解这个应该是搜索. 或者就是递归
然后如果用动态规划写, 这题就是一个 fib 的变种. fib(3) = fib(2) + fib(1) fib(1)不一定能加起来, 因为前两个数不一定在[1,26]