Java-如何递归解码字符串

发布于 2025-02-02 16:31:22 字数 940 浏览 3 评论 0原文

我需要根据计数进行递归编码的字符串，然后

给出一个编码的字符串，任务是解码它。字符串编码的模式如下。

示例：

输入：str [] =“ 1 [b]” 输出：B

输入：str [] =“ 2 [ab] 输出：ABAB

输入：Str [] =“ 2 [A2 [B]” 输出：abbabb

输入：str [] =“ 3 [b2 [ca]]” 输出：

下面的BCACABCACABCACA是我尝试实现同样的代码。我所知道的是，它可以使用两个堆栈来解决。

public class Main {
    public static void main(String[] args) {
        Stack<Interger> s1 = new Stack();
        Stack<String> s2 = new Stack();
        String result = "";
        for(int i = 0; i < args.length; i++){
            if(Interger.parseInt(args[i]) == 0){
                s1.push(args[i]);
            }
            if(args[i] == 0){
                if(args[i] == ']'){
                   result = s2.pop();
                }
                if(args[i] == '['){
                    continue;
                }
                s2.push(args[i])
            }
        }
    }
}

谁能帮助我编写代码以获取预期输出的有效方法是什么？

原文

I need to decode a string recursively encoded as count followed by substring

An encoded string (s) is given, the task is to decode it. The pattern in which the strings are encoded is as follows.

Examples:

Input : str[] = "1[b]"
Output : b

Input : str[] = "2[ab]
Output : abab

Input : str[] = "2[a2[b]]"
Output : abbabb

Input : str[] = "3[b2[ca]]"
Output : bcacabcacabcaca

Below is the code I tried to achieve the same. All I know is it can be solved using two stacks.

public class Main {
    public static void main(String[] args) {
        Stack<Interger> s1 = new Stack();
        Stack<String> s2 = new Stack();
        String result = "";
        for(int i = 0; i < args.length; i++){
            if(Interger.parseInt(args[i]) == 0){
                s1.push(args[i]);
            }
            if(args[i] == 0){
                if(args[i] == ']'){
                   result = s2.pop();
                }
                if(args[i] == '['){
                    continue;
                }
                s2.push(args[i])
            }
        }
    }
}

Can anyone help me what is the efficient way to write code in order to get the expected output?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

天暗了我发光 2025-02-09 16:31:22

如何递归解码

您需要定义A 基本情况和递归情况：

基本情况 - 给定的字符串未包含方括号[]，因此无需处理。返回值是给定的字符串本身。
递归案例 - 我们需要确定打开的索引[和关闭括号]] ，并基于该合同。 /p>

这就是可以实现的方式：

public static String decode(String str) {
    int startOfBrackets = str.indexOf('[');
    
    if (startOfBrackets == -1) { // base case there's no square brackets in the string
        return str;
    }

    int startOfDigits = getFirstDigitsPosition(str);
    int repeatNum = Integer.parseInt(str.substring(startOfDigits, startOfBrackets));
    
    return str.substring(0, startOfDigits) +
        decode(str.substring(startOfBrackets + 1, str.length() - 1)).repeat(repeatNum);
}

public static final Pattern SINGLE_DIGIT = Pattern.compile("\\d");

public static int getFirstDigitsPosition(String str) {
    Matcher matcher = SINGLE_DIGIT.matcher(str);
    if (matcher.find()) {
        return matcher.start();
    }
    return -1;
}

main（）

public static void main(String[] args) {
    System.out.println(decode("1[b]"));
    System.out.println(decode("2[ab]"));
    System.out.println(decode("2[a2[b]]"));
    System.out.println(decode("3[b2[ca]]"));
}

输出：

abab
abbabb
bcacabcacabcaca

How to decode a string recursively

You need to define a base case and recursive case:

Base case - the given string doesn't contain square brackets [], therefore no need to process it. The return value is the given string itself.
Recursive case - we need to determine the indices of opening [ and closing brackets ] and based on that contract a new string.

That's how it could be implemented:

public static String decode(String str) {
    int startOfBrackets = str.indexOf('[');
    
    if (startOfBrackets == -1) { // base case there's no square brackets in the string
        return str;
    }

    int startOfDigits = getFirstDigitsPosition(str);
    int repeatNum = Integer.parseInt(str.substring(startOfDigits, startOfBrackets));
    
    return str.substring(0, startOfDigits) +
        decode(str.substring(startOfBrackets + 1, str.length() - 1)).repeat(repeatNum);
}

public static final Pattern SINGLE_DIGIT = Pattern.compile("\\d");

public static int getFirstDigitsPosition(String str) {
    Matcher matcher = SINGLE_DIGIT.matcher(str);
    if (matcher.find()) {
        return matcher.start();
    }
    return -1;
}

main()

public static void main(String[] args) {
    System.out.println(decode("1[b]"));
    System.out.println(decode("2[ab]"));
    System.out.println(decode("2[a2[b]]"));
    System.out.println(decode("3[b2[ca]]"));
}

Output: