1309-解码字母到整数映射

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:29 2023-09-13 16:06:29 Updated    

给你一个字符串 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"

提示：

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

方法一：遍历

我们对字符串 s 进行顺序遍历。

当遍历到位置 i 时，我们首先向后看两个字符（即 s[i + 2]），如果 s[i + 2] 存在且为 '#'，那么位置 i，i + 1 和 i + 2 表示一个 'j' 到 'z' 之间的字符，否则位置 i 表示一个 'a' 到 'i' 的字符。

根据对 s[i + 2] 的判断，我们可以使用字符串转整数的方法得到对应的字符的 ASCII 码，从而得到字符本身。在这之后，我们将位置 i 后移，继续进行遍历直到结束。

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    string freqAlphabets(string s) {
        string ans;
        for (int i = 0; i < s.size(); ++i) {
            if (i + 2 < s.size() && s[i + 2] == '#') {
                ans += char((s[i] - '0') * 10 + (s[i + 1] - '1') + 'a');
                i += 2;
            }
            else {
                ans += char(s[i] - '1' + 'a');
            }
        }
        return ans;
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def freqAlphabets(self, s: str) -> str:
        def get(st):
            return chr(int(st) + 96)

        i, ans = 0, ""
        while i < len(s):
            if i + 2 < len(s) and s[i + 2] == '#':
                ans += get(s[i : i + 2])
                i += 2
            else:
                ans += get(s[i])
            i += 1
        return ans

复杂度分析

  • 时间复杂度：O(N)，其中 N 是字符串 s 的长度。

  • 空间复杂度：O(1)。

 Comments
On this page
1309-解码字母到整数映射