0030.字符串解压缩.md

30. 字符串解压缩

题目链接

C++

#include<iostream>
#include<sstream>
#include<string>
using namespace std;

string solve(string s) {
    // 记录[ ] |的位置,每次总是会找到最内层的三个
    // 若未找到说明已经完全解压缩,直接返回s
    int x, y, z;
    x = y = z = -1;
    for(int i = 0; i < s.size(); ++i) {
        if(s[i] == '[') {
            x = i;
        }
        else if(s[i] == '|') {
            y = i;
        }
        else if(s[i] == ']') {
            z = i;
            break;
        }
    }
    
    // 必须三个都判断是否全部找到,排除[ ] |作为常规字符的情况
    if(x != -1 && y != -1 && z != -1) {
        // 取出重复数字
        istringstream ss(s.substr(x + 1, y - x));
        int num;
        ss >> num;
        // 将需要重复的字符串取出并且叠加
        string repeat = "";
        string tmp = s.substr(y + 1, z - y - 1);
        for(int i = 0; i < num; ++i) {
            repeat.append(tmp);
        }
        // 前段未处理的部分
        string pre = s.substr(0, x);
        // 后段未处理的部分
        string end = s.substr(z + 1);
        // 与重复的部分组合进行递归
        return solve(pre + repeat + end);
    }
    
    return s;
    
}

int main() {
    string s;
    // 这里一定要getline, 否则遇到空格会断掉读取
    while(getline(cin, s)) {
        string ans = solve(s);
        cout << ans << endl;
    }
    return 0;
}

Java

import java.lang.*;
import java.util.*;

/*

字符串操作，考察设计递归函数的能力。

实现步骤如下：

遍历编码后的字符串，通过记录'['、'|'和']'的位置，找到每个需要重复的子字符串以及重复次数。

如果找到了一组完整的重复字符串信息（即找到了'['、'|'和']'），就将这段信息提取出来，然后根据重复次数和子字符串，构建新的解码后的字符串。

递归地对新构建的解码字符串进行解码，直到没有重复字符串信息为止。

*/

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();
        System.out.print(decode(str));
    }

    public static String decode(String s) {
        int i = 0;
        int x = -1, y = -1, z = -1;

        while (i < s.length()) {
            if (s.charAt(i) == '[') {
                x = i;
            } else if (s.charAt(i) == '|') {
                y = i;
            } else if (s.charAt(i) == ']') {
                z = i;
                break;
            }
            i++;
        }

        if (x != -1 && y != -1 && z != -1) {
            int times = Integer.parseInt(s.substring(x + 1, y));
            String sub = s.substring(y + 1, z);
            StringBuilder decodeStrBuilder = new StringBuilder();

            for (int j = 0; j < times; j++) {
                decodeStrBuilder.append(sub);
            }

            String decodeStr = s.substring(0, x) + decodeStrBuilder.toString() + s.substring(z + 1);
            return decode(decodeStr);
        }
        return s;
    }
}

Python

Go

JS

C