题目

标题和出处

标题：解码字母到整数映射

出处：1309. 解码字母到整数映射

难度

3 级

题目描述

要求

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

• 字符（$\text{‘a’}-\text{‘i’}$）分别用（$\text{‘1’}-\text{‘9’}$）表示。
• 字符（$\text{‘j’}-\text{‘z’}$）分别用（$\text{‘10\#’}-\text{‘26\#’}$）表示。

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

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

示例

示例 1：

输入：$\text{s = "10\#11\#12"}$
输出：$\text{"jkab"}$
解释：$\text{"j"}\to \text{"10\#"}$，$\text{"k"}\to \text{"11\#"}$，$\text{"a"}\to \text{"1"}$，$\text{"b"}\to \text{"2"}$。

示例 2：

输入：$\text{s = "1326\#"}$
输出：$\text{"acz"}$

示例 3：

输入：$\text{s = "25\#"}$
输出：$\text{"y"}$

示例 4：

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

数据范围

• $\text{1}\le \text{s.length}\le \text{1000}$
• $\text{s[i]}$ 只包含数字（$\text{‘0’}-\text{‘9’}$）和 $\text{‘\#’}$ 字符
• $\text{s}$ 是映射始终存在的有效字符串

解法一

思路和算法

由于字符串 $s$ 中包含的数字范围是 $1$ 到 $26$，有一位数和两位数，因此需要区分一位数和两位数，才能得到正确的映射结果。

由于每个一位数都是单个字符，每个两位数后面都有一个 $\text{‘\#’}$ 字符，因此一个简单的映射方法是反向遍历字符串 $s$，解析出所有的一位数和两位数并进行映射。如果当前字符是 $\text{‘\#’}$，则将当前字符的前面两个字符解析成两位数，否则将当前字符解析成一位数，解析得到数字之后，将数字转成对应的字母，然后将下标向前移动到未解析的字符处，继续解析。在移动下标时，如果当前字符是 $\text{‘\#’}$，则将下标向前移动 $3$ 个位置，否则将下标向前移动 $1$ 个位置。

遍历结束之后，即可得到映射之后的全部字母。由于是反向遍历，因此得到的映射之后的全部字母也是反向的，需要将该字符串反转，才能得到映射之后形成的新字符串。

代码

class Solution {
    public String freqAlphabets(String s) {
        StringBuffer sb = new StringBuffer();
        int index = s.length() - 1;
        while (index >= 0) {
            char c = s.charAt(index);
            int num = 0;
            if (c == '#') {
                num = (s.charAt(index - 2) - '0') * 10 + s.charAt(index - 1) - '0';
                index -= 3;
            } else {
                num = c - '0';
                index--;
            }
            sb.append((char) (num - 1 + 'a'));
        }
        return sb.reverse().toString();
    }
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是字符串 $s$ 的长度。需要反向遍历字符串 $s$ 一次，遍历的过程中生成映射之后的新字符串。

• 空间复杂度：$O(n)$，其中 $n$ 是字符串 $s$ 的长度。需要额外创建一个长度为 $O(n)$ 的 $\text{StringBuffer}$ 或 $\text{StringBuilder}$ 类型的对象用于存储映射之后形成的新字符串。由于 Java 中的 $\text{String}$ 类型的对象不可变，因此空间复杂度至少为 $O(n)$。

解法二

思路和算法

也可以正向遍历字符串 $s$，完成解析和映射。遍历过程中，对于每个字符，需要判断该字符是一位数还是两位数的第一个字符，然后解析数字。由于每个两位数后面都有一个 $\text{‘\#’}$ 字符，因此可以通过判断当前字符的后两位的字符是不是 $\text{‘\#’}$ 的方法判断当前字符是一位数还是两位数的第一个字符。

具体做法为，对于遍历到的字符，如果其后两位的字符是 $\text{‘\#’}$，则将当前字符和后一位的字符解析成两位数，然后将下标向后移动 $3$ 个位置，否则将当前字符解析成一位数，然后将下标向后移动 $1$ 个位置。遍历结束之后，即可得到映射之后形成的新字符串。

代码

class Solution {
    public String freqAlphabets(String s) {
        StringBuffer sb = new StringBuffer();
        int length = s.length();
        int index = 0;
        while (index < length) {
            int num = 0;
            if (index + 2 < length && s.charAt(index + 2) == '#') {
                num = (s.charAt(index) - '0') * 10 + s.charAt(index + 1) - '0';
                index += 3;
            } else {
                num = s.charAt(index) - '0';
                index++;
            }
            sb.append((char) (num - 1 + 'a'));
        }
        return sb.toString();
    }
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是字符串 $s$ 的长度。需要正向遍历字符串 $s$ 一次，遍历的过程中生成映射之后的新字符串。

• 空间复杂度：$O(n)$，其中 $n$ 是字符串 $s$ 的长度。需要额外创建一个长度为 $O(n)$ 的 $\text{StringBuffer}$ 或 $\text{StringBuilder}$ 类型的对象用于存储映射之后形成的新字符串。由于 Java 中的 $\text{String}$ 类型的对象不可变，因此空间复杂度至少为 $O(n)$。