(C卷,100分)- 一种字符串压缩表示的解压（Java & JS & Python）

题目描述

有一种简易压缩算法：针对全部由小写英文字母组成的字符串，将其中连续超过两个相同字母的部分压缩为连续个数加该字母，其他部分保持原样不变。

例如：字符串“aaabbccccd”经过压缩成为字符串“3abb4cd”。

请您编写解压函数，根据输入的字符串，判断其是否为合法压缩过的字符串，

若输入合法则输出解压缩后的字符串，否则输出字符串“!error”来报告错误。

输入描述

输入一行，为一个ASCII字符串，长度不会超过100字符，用例保证输出的字符串长度也不会超过100字符。

输出描述

若判断输入为合法的经过压缩后的字符串，则输出压缩前的字符串；

若输入不合法，则输出字符串“!error”。

用例

题目解析

简单的字符串操作题，难度在于如何将输入压缩字符串中4d这种子串找到并替换为dddd，我这里用的正则的捕获组。

同时生成重复字符的字符串，发现了一个好方法，即：

new Array(重复次数).fill(重复字符)

比如 new Array(4).fill('d') 就可以生成 'dddd'

2023.05.25

给几个用例：3bb，bbb，3b4b

大家觉得这几个压缩字符串是合法的吗？

答案是不合法，原因很简单，我们将他们解压后，再按照题目要求重新压缩，得到的压缩字符串和这些是不一样的，比如3bb，解压后为bbbb，再次压缩后为4b。

因此，我们只能得到解压字符串后，还需要重新压缩，来对比输入的字符串，如果不一样，则说明输入的压缩字符串不合法，需要返回!error

2024.1.15

下面代码中，当我们用正则匹配到：数字+字母，比如4d，后面进行了字符串替换，将字符串中所有4d替换为了dddd，这是有问题的，比如输入串为 4d5a14d，进行4d替换后，就变为dddd5a1dddd，这是不正确的，因为后面的14d被错误替换为1dddd了，因此我们进行字符串替换操作时，只能进行首次替换。

JS算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on("line", (line) => {
  console.log(getResult(line));
});

function getResult(str) {
  // 对字符串进行备份
  const back_str = str;

  // 压缩字符串str只能包含小写字母和数字，如果包含其他字符则非法
  if (/[^a-z0-9]/.test(str)) {
    return "!error";
  }

  // 该正则用于匹配 “4a”，“12b” 这种 “数字+小写字母” 的子串
  const regExp = /(d+)([a-z])?/g;

  while (true) {
    const res = regExp.exec(str);

    if (!res) break;

    // 要被替换的压缩子串
    const src = res[0];

    const repeat_times = res[1] - 0;

    // 压缩字符串中不会存在0，1，2
    if (repeat_times <= 2) {
      return "!error";
    }

    const repeat_content = res[2];
    // abc4这种情况视为异常
    if (!repeat_content) return "!error";

    // // 替换后的解压子串
    const tar = new Array(repeat_times).fill(repeat_content).join("");

    str = str.replace(src, tar);
  }

  // 如果解压字符串重新压缩后，和输入的压缩子串不一样，则说明输入的压缩字符串不合法，比如输入为3bb，bbb, 3b4b都是不合法
  if (zip(str) != back_str) return "!error";

  return str;
}

// 压缩字符串
function zip(str) {
  str += "-";

  const ans = [];

  const stack = [];
  let repeat = 0;

  for (let c of str) {
    if (stack.length == 0) {
      stack.push(c);
      repeat++;
      continue;
    }

    // stack.length > 0
    const top = stack.at(-1);
    if (top == c) {
      repeat++;
      continue;
    }

    // top != c
    if (repeat > 2) {
      ans.push(`${repeat}${top}`);
    } else {
      ans.push(...new Array(repeat).fill(top));
    }
    stack.length = 0;
    stack.push(c);
    repeat = 1;
  }

  return ans.join("");
}

Java算法源码

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.println(getResult(sc.next()));
  }

  public static String getResult(String str) {
    String back_str = str;

    // 压缩字符串str只能包含小写字母和数字 ，如果包含其他字符则非法
    if (!str.matches("[a-z0-9]+")) {
      return "!error";
    }

    // 该正则用于匹配 “4a”，“12b” 这种 “数字+小写字母” 的子串
    Pattern p = Pattern.compile("(\d+)([a-z])?");

    while (true) {
      Matcher m = p.matcher(str);

      if (!m.find()) break;

      // 要被替换的压缩子串
      String src = m.group();

      int repeat_times = Integer.parseInt(m.group(1));
      // 连续超过两个相同字母的部分压缩为连续个数加该字母，因此不可能出现0，1，2的情况
      if (repeat_times < 3) return "!error";

      String repeat_content = m.group(2);
      // a4这种情况视为异常
      if (repeat_content == null) return "!error";

      // 替换后的解压子串
      StringBuilder sb = new StringBuilder();
      for (int i = 0; i < repeat_times; i++) sb.append(repeat_content);

      str = str.replaceFirst(src, sb.toString());
    }

    // 如果解压字符串重新压缩后，和输入的压缩子串不一样，则说明输入的压缩字符串不合法，比如输入为3bb，bbb, 3b4b都是不合法
    if (!zip(str).equals(back_str)) return "!error";

    return str;
  }

  public static String zip(String str) {
    str += "-";

    StringBuilder ans = new StringBuilder();

    LinkedList<Character> stack = new LinkedList<>();
    int repeat = 0;

    for (int i = 0; i < str.length(); i++) {
      char c = str.charAt(i);

      if (stack.size() == 0) {
        stack.add(c);
        repeat++;
        continue;
      }

      // stack.size() > 0
      char top = stack.getLast();

      if (top == c) {
        repeat++;
        continue;
      }

      // top != c
      if (repeat > 2) {
        ans.append(repeat).append(top);
      } else {
        char[] tmp = new char[repeat];
        Arrays.fill(tmp, top);
        ans.append(new String(tmp));
      }
      stack.clear();
      stack.add(c);
      repeat = 1;
    }

    return ans.toString();
  }
}

Python算法源码

import re

# 输入获取
s = input()


# 压缩字符串
def zip(src):
    src += "-"

    ans = []
    stack = []
    repeat = 0

    for c in src:
        if len(stack) == 0:
            stack.append(c)
            repeat += 1
            continue

        # stack.length > 0
        top = stack[-1]
        if top == c:
            repeat += 1
            continue

        # top != c
        if repeat > 2:
            ans.append(f"{repeat}{top}")
        else:
            ans.append("".join([top] * repeat))

        stack.clear()
        stack.append(c)
        repeat = 1

    return "".join(ans)


# 算法入口
def getResult():
    # 对字符串进行备份
    back_s = s

    # 压缩字符串str只能包含小写字母和数字，如果包含其他字符则非法
    if re.search(r"[^a-z0-9]", back_s) is not None:
        return "!error"

    # 该正则用于匹配 “4a”，“12b” 这种 “数字+小写字母” 的子串
    reg = re.compile(r"(d+)([a-z])?")

    while True:
        match = reg.search(back_s)

        if match is None:
            break

        # 要被替换的压缩子串
        src = match.group()
        repeat_times = int(match.group(1))

        # 压缩字符串中不会存在0，1，2
        if repeat_times <= 2:
            return "!error"

        repeat_content = match.group(2)

        #  abc4这种情况视为异常
        if repeat_content is None:
            return "!error"

        # 替换后的解压子串
        tar = "".join([repeat_content] * repeat_times)

        back_s = back_s.replace(src, tar, 1)

    # 如果解压字符串重新压缩后，和输入的压缩子串不一样，则说明输入的压缩字符串不合法，比如输入为3bb，bbb, 3b4b都是不合法
    if zip(back_s) != s:
        return "!error"
    else:
        return back_s


# 算法调用
print(getResult())