1309-解码字母到整数映射

Raphael Liu Lv10

给你一个字符串 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] 存在且为 '#',那么位置 ii + 1i + 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-解码字母到整数映射