1309. 解码字母到整数映射

Hi 大家好，我是张小猪。欢迎来到『宝宝也能看懂』系列之 leetcode 周赛题解。

这里是第 170 期的第 1 题，也是题目列表中的第 1309 题 -- 『解码字母到整数映射』

题目描述

给你一个字符串 s，它由数字（'0' - '9'）和 '#' 组成。我们希望按下述规则将 s 映射为一些小写英文字符：

• 字符（'a' - 'i'）分别用（'1' - '9'）表示。
• 字符（'j' - 'z'）分别用（'10#' - '26#'）表示。

返回映射之后形成的新字符串。

题目数据保证映射始终唯一。

示例 1：

输入：s = "10#11#12"
输出："jkab"
解释："j" -> "10#" , "k" -> "11#" , "a" -> "1" , "b" -> "2".

示例 2：

输入：s = "1326#"
输出："acz"

示例 3：

输入：s = "25#"
输出："y"

示例 4：

输入：s = "12345678910#11#12#13#14#15#16#17#18#19#20#21#22#23#24#25#26#"
输出："abcdefghijklmnopqrstuvwxyz"

提示：

• 1 <= s.length <= 1000
• s[i] 只包含数字（'0'-'9'）和 '#' 字符。
• s 是映射始终存在的有效字符串。

官方难度

EASY

解决思路

这道题非常直白，是处理一个从数字到字符串的映射关系。其中映射区间分为两段，[1, 9] 和 [10, 26]，而后者会用一个后置的 '#' 符号进行标识区分。

读完题目，我的第一反应是，那我们先搞个字典用于记录和查询映射关系吧。免得每次使用或者转换的时候都需要去计算。

在喊出魔法咒语『巴拉巴拉 张小猪是最美(pang)的』之后，我的编辑器里就出现了下面这个字典。

const map = {"1":"a","2":"b","3":"c","4":"d","5":"e","6":"f","7":"g","8":"h","9":"i","10":"j","11":"k","12":"l","13":"m","14":"n","15":"o","16":"p","17":"q","18":"r","19":"s","20":"t","21":"u","22":"v","23":"w","24":"x","25":"y","26":"z"};

大家也可以试一试啦。要是万一不行的话，通过一个循环结合 JSON.stringify 应该可以很容易生成这个字符串。我这里就不贴相关的代码啦，才不是因为我忘记保留并且又懒得再敲一遍了呢（确信脸）

有了上面这个字典之后，我们该如何进行字符串的遍历和转换呢？下面提供三种不同的思路，方便小伙伴们发散思维和取舍。也欢迎小伙伴们分享更多有意思的思路，小猪在此先行阿里嘎多。

基于 stack 实现

这种实现思路是，基于 stack 这种数据结构的特点，即 FILO（先进后出），来处理后置 '#' 这个特殊字符，从而区分两个不同的映射区间，最终实现我们的目标。具体流程如下：

1. 从头开始遍历原始字符串。

2. 对所有遇到的数字进行入栈操作。

   • 如果遇到了数字，则进行入栈操作。
   • 如果遇到了 '#' 这个特殊字符，进行两次出栈操作，并将得到的内容拼接后进行 [10, 26] 区间的映射转换，将映射结果重新入栈。

3. 当遍历完原始字符串后，对当前栈不断的执行出栈操作。

   • 如果遇到数字进行 [1, 9] 区间的映射转换，然后进行拼接
   • 如果数字则直接进行拼接。
4. 返回最终拼接好的结果。

基于该流程可以写出类似如下的代码：

const freqAlphabets = s => {
  const stack = [];
  for (const char of s) {
    if (char !== '#') { stack.push(char); continue; }
    const digit = stack.pop();
    stack.push(map[(stack.pop() + digit)]);
  }
  let ret = '';
  for (const char of stack) {
    ret += char <= '9' ? map[char] : char;
  }
  return ret;
};

这里顺便说一下，这种思路其实是一种处理字符串遍历中后置特殊判断的相对通用思路。相信小伙们在刷题过程中应该还能再遇到可以基于这个思路解决的问题。Fighting!

基于本题的逻辑直接遍历实现

针对本题具体的逻辑，其实可以进行更简单的直接实现。具体流程如下：

1. 从头开始遍历原始字符串。

2. 检测 i + 2 这个下标是否为特殊字符 '#'。

   • 如果不是则进行 [0, 9] 区间的映射转换，然后进行拼接。
   • 如果是则对 i 和 i + 1 进行 [10, 26] 区间的映射转换，然后进行拼接，注意跳过 i + 2。
3. 返回最终拼接好的字符串。

基于该流程可以写出类似如下的代码：

const freqAlphabets = s => {
  let ret = '';
  for (let i = 0; i < s.length; ++i) {
    ret += map[s[i + 2] === '#' ? (i += 2, s[i - 2] + s[i - 1]) : s[i]];
  }
  return ret;
};

基于正则表达式实现

这个思路就非常简单啦，基于正则表达式做一个匹配、转换和替换即可。由于 JS 中字符串的 replace 方法支持正则，于是可以直接实现类似如下的代码：

const freqAlphabets = s => s.replace(/(\d\d#|\d)/g, t => map[t.length === 3 ? t[0] + t[1] : t]);

总结

周赛第一题，惯例的保底送分题。所以就尝试从不同的思路给予一些方案。
不过这篇文章的核心点是引入『巴拉巴拉 张小猪是最美(pang)的』这句魔法咒语，以便后续使用 >.<

相关链接

• Weekly Contest 170 题目列表
• 系列题解 repo
• 我的 segmentfault 专栏
• 我的知乎专栏