LeetCode 1309: Decrypt String from Alphabet to Integer Mapping (Right-to-Left # Parsing)
LeetCode 1309StringParsingToday we solve LeetCode 1309 - Decrypt String from Alphabet to Integer Mapping.
Source: https://leetcode.com/problems/decrypt-string-from-alphabet-to-integer-mapping/
English
Problem Summary
Given a string s where '1' - '9' map to 'a' - 'i' and '10#' - '26#' map to 'j' - 'z', decode the whole string.
Key Insight
When scanning from right to left, # immediately tells us we must consume exactly two previous digits as one letter. This removes ambiguity and keeps parsing simple.
Algorithm
- Start from the end of the string.
- If current char is #, parse the two digits before it as a number in [10,26], convert to letter, and move left by 3.
- Otherwise parse one digit in [1,9], convert to letter, and move left by 1.
- Reverse the built characters at the end.
Complexity Analysis
Let n be the length of s.
Time: O(n).
Space: O(n) for the output buffer.
Common Pitfalls
- Forgetting to reverse when scanning from right to left.
- Parsing two-digit values without checking the trailing #.
- Off-by-one errors when moving the pointer after #.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public String freqAlphabets(String s) {
StringBuilder sb = new StringBuilder();
int i = s.length() - 1;
while (i >= 0) {
if (s.charAt(i) == '#') {
int num = (s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0');
sb.append((char) ('a' + num - 1));
i -= 3;
} else {
int num = s.charAt(i) - '0';
sb.append((char) ('a' + num - 1));
i -= 1;
}
}
return sb.reverse().toString();
}
}func freqAlphabets(s string) string {
out := make([]byte, 0, len(s))
for i := len(s) - 1; i >= 0; {
if s[i] == '#' {
num := int(s[i-2]-'0')*10 + int(s[i-1]-'0')
out = append(out, byte('a'+num-1))
i -= 3
} else {
num := int(s[i] - '0')
out = append(out, byte('a'+num-1))
i--
}
}
for l, r := 0, len(out)-1; l < r; l, r = l+1, r-1 {
out[l], out[r] = out[r], out[l]
}
return string(out)
}class Solution {
public:
string freqAlphabets(string s) {
string out;
for (int i = (int)s.size() - 1; i >= 0; ) {
if (s[i] == '#') {
int num = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
out.push_back(char('a' + num - 1));
i -= 3;
} else {
int num = s[i] - '0';
out.push_back(char('a' + num - 1));
i -= 1;
}
}
reverse(out.begin(), out.end());
return out;
}
};class Solution:
def freqAlphabets(self, s: str) -> str:
out = []
i = len(s) - 1
while i >= 0:
if s[i] == '#':
num = int(s[i - 2:i])
out.append(chr(ord('a') + num - 1))
i -= 3
else:
num = int(s[i])
out.append(chr(ord('a') + num - 1))
i -= 1
return ''.join(reversed(out))var freqAlphabets = function(s) {
const out = [];
for (let i = s.length - 1; i >= 0;) {
if (s[i] === '#') {
const num = Number(s.slice(i - 2, i));
out.push(String.fromCharCode('a'.charCodeAt(0) + num - 1));
i -= 3;
} else {
const num = Number(s[i]);
out.push(String.fromCharCode('a'.charCodeAt(0) + num - 1));
i -= 1;
}
}
out.reverse();
return out.join('');
};中文
题目概述
给定字符串 s，其中 '1' - '9' 映射为 'a' - 'i'，'10#' - '26#' 映射为 'j' - 'z'，要求解码出原字符串。
核心思路
从右往左扫描时，遇到 # 就能确定必须把它前面的两位数字作为一个整体字母来解析，避免歧义。
算法步骤
- 从字符串末尾开始遍历。
- 若当前位置是 #，取前两位组成 10~26，映射成字母，指针左移 3。
- 否则取单个数字 1~9 映射成字母，指针左移 1。
- 最后将结果反转得到答案。
复杂度分析
设字符串长度为 n。
时间复杂度：O(n)。
空间复杂度：O(n)（结果缓冲区）。
常见陷阱
- 右向左构建后忘记反转。
- 没有根据 # 来判断两位数映射，导致错误分段。
- 指针移动步长写错，造成越界或漏解析。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public String freqAlphabets(String s) {
StringBuilder sb = new StringBuilder();
int i = s.length() - 1;
while (i >= 0) {
if (s.charAt(i) == '#') {
int num = (s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0');
sb.append((char) ('a' + num - 1));
i -= 3;
} else {
int num = s.charAt(i) - '0';
sb.append((char) ('a' + num - 1));
i -= 1;
}
}
return sb.reverse().toString();
}
}func freqAlphabets(s string) string {
out := make([]byte, 0, len(s))
for i := len(s) - 1; i >= 0; {
if s[i] == '#' {
num := int(s[i-2]-'0')*10 + int(s[i-1]-'0')
out = append(out, byte('a'+num-1))
i -= 3
} else {
num := int(s[i] - '0')
out = append(out, byte('a'+num-1))
i--
}
}
for l, r := 0, len(out)-1; l < r; l, r = l+1, r-1 {
out[l], out[r] = out[r], out[l]
}
return string(out)
}class Solution {
public:
string freqAlphabets(string s) {
string out;
for (int i = (int)s.size() - 1; i >= 0; ) {
if (s[i] == '#') {
int num = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
out.push_back(char('a' + num - 1));
i -= 3;
} else {
int num = s[i] - '0';
out.push_back(char('a' + num - 1));
i -= 1;
}
}
reverse(out.begin(), out.end());
return out;
}
};class Solution:
def freqAlphabets(self, s: str) -> str:
out = []
i = len(s) - 1
while i >= 0:
if s[i] == '#':
num = int(s[i - 2:i])
out.append(chr(ord('a') + num - 1))
i -= 3
else:
num = int(s[i])
out.append(chr(ord('a') + num - 1))
i -= 1
return ''.join(reversed(out))var freqAlphabets = function(s) {
const out = [];
for (let i = s.length - 1; i >= 0;) {
if (s[i] === '#') {
const num = Number(s.slice(i - 2, i));
out.push(String.fromCharCode('a'.charCodeAt(0) + num - 1));
i -= 3;
} else {
const num = Number(s[i]);
out.push(String.fromCharCode('a'.charCodeAt(0) + num - 1));
i -= 1;
}
}
out.reverse();
return out.join('');
};
Comments