Java - How to decode a string recursively

user_6313539 0
Viewed 107

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?

recursion data-structures stack algorithm java
1 Answers

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:

abab
abbabb
bcacabcacabcaca
user_179499450
Related