你的位置:首页 > 信息动态 > 新闻中心
信息动态
联系我们

字符串题目:解码字母到整数映射

2021-12-2 7:07:16

文章目录

  • 题目
    • 标题和出处
    • 难度
    • 题目描述
      • 要求
      • 示例
      • 数据范围
  • 解法一
    • 思路和算法
    • 代码
    • 复杂度分析
  • 解法二
    • 思路和算法
    • 代码
    • 复杂度分析

题目

标题和出处

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

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

难度

3 级

题目描述

要求

给你一个字符串 s \texttt{s} s,它由数字( ‘0’ − ‘9’ \texttt{`0'} - \texttt{`9'} ‘0’‘9’)和 ‘#’ \texttt{`\#'} ‘#’ 组成。我们希望按下述规则将 s \texttt{s} s 映射为一些小写英文字符:

  • 字符( ‘a’ − ‘i’ \texttt{`a'} - \texttt{`i'} ‘a’‘i’)分别用( ‘1’ − ‘9’ \texttt{`1'} - \texttt{`9'} ‘1’‘9’)表示。
  • 字符( ‘j’ − ‘z’ \texttt{`j'} - \texttt{`z'} ‘j’‘z’)分别用( ‘10#’ − ‘26#’ \texttt{`10\#'} - \texttt{`26\#'} ‘10#’‘26#’)表示。

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

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

示例

示例 1:

输入: s   =   "10#11#12" \texttt{s = "10\#11\#12"} s = "10#11#12"
输出: "jkab" \texttt{"jkab"} "jkab"
解释: "j" → "10#" \texttt{"j"} \rightarrow \texttt{"10\#"} "j""10#" "k" → "11#" \texttt{"k"} \rightarrow \texttt{"11\#"} "k""11#" "a" → "1" \texttt{"a"} \rightarrow \texttt{"1"} "a""1" "b" → "2" \texttt{"b"} \rightarrow \texttt{"2"} "b""2"

示例 2:

输入: s   =   "1326#" \texttt{s = "1326\#"} s = "1326#"
输出: "acz" \texttt{"acz"} "acz"

示例 3:

输入: s   =   "25#" \texttt{s = "25\#"} s = "25#"
输出: "y" \texttt{"y"} "y"

示例 4:

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

数据范围

  • 1 ≤ s.length ≤ 1000 \texttt{1} \le \texttt{s.length} \le \texttt{1000} 1s.length1000
  • s[i] \texttt{s[i]} s[i] 只包含数字( ‘0’ − ‘9’ \texttt{`0'} - \texttt{`9'} ‘0’‘9’)和 ‘#’ \texttt{`\#'} ‘#’ 字符
  • s \texttt{s} s 是映射始终存在的有效字符串

解法一

思路和算法

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

由于每个一位数都是单个字符,每个两位数后面都有一个 ‘#’ \text{`\#'} ‘#’ 字符,因此一个简单的映射方法是反向遍历字符串 s s s,解析出所有的一位数和两位数并进行映射。如果当前字符是 ‘#’ \text{`\#'} ‘#’,则将当前字符的前面两个字符解析成两位数,否则将当前字符解析成一位数,解析得到数字之后,将数字转成对应的字母,然后将下标向前移动到未解析的字符处,继续解析。在移动下标时,如果当前字符是 ‘#’ \text{`\#'} ‘#’,则将下标向前移动 3 3 3 个位置,否则将下标向前移动 1 1 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 ) O(n) O(n),其中 n n n 是字符串 s s s 的长度。需要反向遍历字符串 s s s 一次,遍历的过程中生成映射之后的新字符串。

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

解法二

思路和算法

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

具体做法为,对于遍历到的字符,如果其后两位的字符是 ‘#’ \text{`\#'} ‘#’,则将当前字符和后一位的字符解析成两位数,然后将下标向后移动 3 3 3 个位置,否则将当前字符解析成一位数,然后将下标向后移动 1 1 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 ) O(n) O(n),其中 n n n 是字符串 s s s 的长度。需要正向遍历字符串 s s s 一次,遍历的过程中生成映射之后的新字符串。

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