Easy

题目描述

给你一个由数字和 ‘#’ 组成的字符串 s，你需要将 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 只含有数字和字符 ‘#’。
  • s 是一个有效字符串，映射总是存在。

解题思路

这道题的关键是理解编码规则：

  • ‘a’-‘i’ 对应 ‘1’-‘9’
  • ‘j’-‘z’ 对应 ‘10#’-‘26#’

有两种常见解法：

方法一：从右到左扫描（推荐） 从字符串末尾开始扫描，每次检查当前位置往后2位是否是’#’：

  • 如果是’#’，则当前位置和前一位组成两位数字（如"10#"）
  • 如果不是’#’，则当前位置是单个数字

这种方法的优势是避免了向前看的复杂性，因为’#‘总是在两位数的末尾。

方法二：从左到右扫描 从左到右扫描，需要向前看2位判断是否有’#’：

  • 如果当前位置+2是’#’，处理两位数
  • 否则处理单位数

两种方法时间复杂度相同，但从右到左的方法实现更简洁。

核心思路是正确识别编码模式，然后将数字转换为对应的字母：数字n对应第n个字母，即’a’+n-1。

代码实现

class Solution {
public:
    string freqAlphabets(string s) {
        string result = "";
        int i = s.length() - 1;
        
        while (i >= 0) {
            if (i >= 2 && s[i] == '#') {
                // 处理两位数字
                int num = (s[i-2] - '0') * 10 + (s[i-1] - '0');
                result = char('a' + num - 1) + result;
                i -= 3;
            } else {
                // 处理单位数字
                int num = s[i] - '0';
                result = char('a' + num - 1) + result;
                i--;
            }
        }
        
        return result;
    }
};

class Solution:
    def freqAlphabets(self, s: str) -> str:
        result = []
        i = len(s) - 1
        
        while i >= 0:
            if i >= 2 and s[i] == '#':
                # 处理两位数字
                num = int(s[i-2:i])
                result.append(chr(ord('a') + num - 1))
                i -= 3
            else:
                # 处理单位数字
                num = int(s[i])
                result.append(chr(ord('a') + num - 1))
                i -= 1
        
        return ''.join(reversed(result))

public class Solution {
    public string FreqAlphabets(string s) {
        var result = new StringBuilder();
        int i = s.Length - 1;
        
        while (i >= 0) {
            if (i >= 2 && s[i] == '#') {
                // 处理两位数字
                int num = (s[i-2] - '0') * 10 + (s[i-1] - '0');
                result.Insert(0, (char)('a' + num - 1));
                i -= 3;
            } else {
                // 处理单位数字
                int num = s[i] - '0';
                result.Insert(0, (char)('a' + num - 1));
                i--;
            }
        }
        
        return result.ToString();
    }
}

var freqAlphabets = function(s) {
    let result = "";
    let i = s.length - 1;
    
    while (i >= 0) {
        if (i >= 2 && s[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大O表示法说明
时间复杂度O(n)需要遍历字符串一次，每个字符最多访问一次
空间复杂度O(n)需要额外空间存储结果字符串