字符串解码问题

时间:2022-12-23 22:07:49

作者:Grey

原文地址:

博客园:字符串解码问题

CSDN:字符串解码问题

题目描述

给定一个经过编码的字符串,返回它解码后的字符串。

编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。

此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入。

示例 1:

输入:s = "3[a]2[bc]"
输出:"aaabcbc"
示例 2:

输入:s = "3[a2[c]]"
输出:"accaccacc"
示例 3:

输入:s = "2[abc]3[cd]ef"
输出:"abcabccdcdcdef"
示例 4:

输入:s = "abc3[cd]xyz"
输出:"abccdcdcdxyz"

题目链接见:LeetCode 394. Decode String

主要思路

定义递归函数

String[] p(char[] str, int n, int from)

递归含义表示,str 字符串从 from 开始一直到结尾或者右边括号生成的信息返回,返回值是一个长度为 2 的数组,例如

2[abc]3[cd]ef

这个字符串,递归函数在执行过程中,遇到第一个右括号的时候,就会结算出两个信息,

第一个信息:之前处理过的字符串是什么;

第二个信息:处理到了哪个位置。

所以,在经历第一次递归过程后,返回

String[] res

其中

res[0] = "abcabc"; // 第一次遇到],进行结算生成的字符串
res[1] = "5" // 处理到了第五个位置,即第一个]出现的位置

继续递归

res[0] = "abcabccdcdcd"; // 第二次遇到],进行结算生成的字符串,注:这里要拼接上上一次递归的"abcabc"
res[1] = "10" // 处理到了第十个位置,即第二个]出现的位置

继续,后续没有]了,所以一直到字符串最后,得到最终的结果

res[0] = "abcabccdcdcdef"; // 处理到了终止位置,结算之前拼接的字符串和最后遗留字符串拼接的最终结果
res[1] = "12"; // 处理到了终止位置

完整代码如下

class Solution {
  
  public static String decodeString(String s) {
    char[] str = s.toCharArray();
    int len = str.length;
    return p(str, len, 0)[0];
  }

  private static String[] p(char[] str, int n, int from) {
    StringBuilder sb = new StringBuilder();
    int pre = 0;
    int i = from;
    while (i != n && str[i] != ']') {
      if (Character.isLowerCase(str[i]) || Character.isUpperCase(str[i])) {
        // 字母
        sb.append(str[i++]);
      } else if (Character.isDigit(str[i])) {
        // 数字
        pre = pre * 10 + Integer.parseInt(String.valueOf(str[i++]));
      } else if ('[' == str[i]) {
        // 左括号
        String[] bra = p(str, n, i + 1);
        sb.append(build(pre, bra[0]));
        pre = 0;
        i = Integer.parseInt(bra[1]) + 1;
      }
    }
    return new String[] {sb.toString(), String.valueOf(i)};
  }

  private static String build(int pre, String s) {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < pre; i++) {
      sb.append(s);
    }
    return sb.toString();
  }

}

代码说明

主要看p函数的while循环部分,其中i != n && str[i] != ']'就是控制每次递归只处理除了结尾位置和]位置的其他位置,遇到结尾或者]直接返回一次结算结果。

while中的三个分支也比较直白,对于字母的话,直接append就可以,对于数字,要处理一个简单的边界条件,即数字不一定是单个整数,可能是多位数,比如334[abc],对于[,就可以结算这个[匹配的右括号之间的内容:

        // 得到与其匹配的右括号之间的内容
        String[] bra = p(str, n, i + 1);
        sb.append(build(pre, bra[0]));
        pre = 0;
        // 去下一个位置匹配
        i = Integer.parseInt(bra[1]) + 1;

更多

算法和数据结构笔记