java - 可嵌套数据集的字符串压缩与解压

Question

我输入的是一个格式为number[string]的压缩字符串，解压后的输出形式应该是字符串被写入number次。例如:

3[abc]4[ab]c = abcabcabcababababc

2[3[a]b] = aaabaaab.

我在 Java 中的暴力破解方法:

public class CompresnDecompresn {

    public static void main(String[] args) {

        String s="3[abc]4[ab]c";
        for (int i = 0; i<s.length(); i++)  {
            if(s.charAt(i)==']') {
                int j=i-1;
                while(true)  {
                    if(s.charAt(j)=='[') {
                        break;
                    }
                    j--;
                }
                int k=j-1;
                while(true) {
                    if(k<0) {
                        break;
                    }
                    int m=(int)s.charAt(k);
                    if(m<48 || m>57) {
                        break;
                    }
                    k--;
                }
                k++;
                int freq=Integer.parseInt(s.substring(k, j));
                String snippet=s.substring(j+1,i);
                String temp="";

                for (int l = 0; l < freq; l++) {
                    temp+=snippet;
                }
                s=s.substring(0,k)+temp+s.substring(i+1);
            }
        }        
        System.out.println(s);                
    }    
}

我能否以更低的成本获得更好的方法？

Answer 1

由于您使用 Java，请随意使用 Java 提供的功能来使解决方案更具可读性和直接性。这里采用 Regex 并使用 StringBuilder 连接字符串。

考虑输入 String string ="3[abc]4[ab]c"; 就我个人而言，我会选择这样的输入:

首先定义保存数字字母对的Couple类。

private static class Couple {

    public int x;
    public String y;

    public Couple(int x, String y) {
        this.x = x;
        this.y = y;
    }
}

我们开始吧:

// Regex to extract the number before '[' and the content inside of '[]'
Pattern p = Pattern.compile("(\\d+)\\[(.*?)\\]");
Matcher m = p.matcher(string);

// Coupling the number and the letters
List<Couple> couples = new ArrayList<>();
while (m.find()) {
    couples.add(new Couple(Integer.parseInt(m.group(1)), m.group(2)));
}

// Concatenating String together using the for-cycle
String rest = string.substring(string.lastIndexOf("]")+1, string.length());
StringBuilder sb = new StringBuilder();

for (Couple c: couples) {
    for (int i=0; i<c.x; i++) {
        sb.append(c.y);
    }
}

// Enjoying the result
sb.append(rest);
System.out.println(sb.toString());

请记住，这只是解决您的问题的一个愚蠢天真的解决方案，以防输入字符串的格式始终为

number[string]number[string]number[string]rest // more of number[string] pairs

您必须全面考虑是否有需要注意失败代码的地方。如果没有 rest 怎么办？如果用户的输入格式不同(永远不要相信用户的输入)怎么办——那么是否值得针对 Regex 对其进行验证？您必须从如果发生什么事情开始问自己问题。

无论如何，您可以从我的实现开始，然后根据需要继续。