Decode String in Java

Question

I am trying to convert this Python Solution in Java. For some reason, my Java Solution is not working. How can this be done correctly?

https://leetcode.com/problems/decode-string/description/

Given an encoded string, return its decoded string. The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; there are no extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there will not be input like 3a or 2[4].

The test cases are generated so that the length of the output will never exceed 105.

Example 1:

Input: s = "3[a]2[bc]"
Output: "aaabcbc"
Example 2:

Input: s = "3[a2[c]]"
Output: "accaccacc"

Python Solution:

class Solution: def decodeString(self, s: str) -> str: stack = []

    for char in s:
        if char is not "]":
            stack.append(char)
        else:
            sub_str = ""
            while stack[-1] is not "[":
                sub_str = stack.pop() + sub_str
            stack.pop()

            multiplier = ""
            while stack and stack[-1].isdigit():
                multiplier = stack.pop() + multiplier

            stack.append(int(multiplier) * sub_str)

    return "".join(stack)

Java Attempt:

class Solution {
    public String decodeString(String s) {
        Deque<String> list = new ArrayDeque<String>();
        String subword = "";
        String number = "";

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != ']' ) {
                list.add(String.valueOf(s.charAt(i)));
            }
            else {
                subword = "";
                while (list.size() > 0 && !list.getLast().equals("[") ) {
                    subword = list.pop() + subword;
                }
                if (list.size() > 0) list.pop();

                number = "";
                while (list.size() > 0 && isNumeric(list.getLast())){
                    number = list.pop() + number;
                }
                for (int j = 1; (isNumeric(number) && j <= Integer.parseInt(number)); j++) list.add(subword);   

            }
        }
        return String.join("", list);
    }

    public static boolean isNumeric(String str) { 
        try {  
            Double.parseDouble(str);  
            return true;
        } catch(NumberFormatException e){  
            return false;  
        }  
    }   
}

As a side note, `char is not "]"` is bad Python code. It relies on an implementation-specific optimization and isn't guaranteed to work as expected (see [string interning](https://stackoverflow.com/q/15541404/11082165)). In fact, in Python 3.9+, this code will result in a `SyntaxWarning`. Use `char != "]"` instead — Brian61354270, Jan 16 '23 at 20:18

Jake Henry · Accepted Answer · 2023-01-17T14:19:22.353

1

The reason why your posted code is not working is because the pop() method in python removes the last element by default.

But in Java, the ArrayDeque class's pop() method removes the first element.

In order to emulate the python code with the ArrayDeque, you'll need to use the removeLast() method of the ArrayDeque instance instead.

edited Jan 17 '23 at 14:19

answered Jan 16 '23 at 20:47

Jake Henry

303
1
10

I am trying to take the python code above, and convert/port it, this is a different answer solution – mattsmith5 Jan 16 '23 at 21:18
@mattsmith5 My apologies. The reason your code is not working is because you need to use the method 'removeLast' instead of 'pop'. In python pop removes the last element, but in Java it removes the first (for an ArrayDeque). – Jake Henry Jan 16 '23 at 21:51
ok,feel free to rewrite ansewr, and I can send points, thanks – mattsmith5 Jan 17 '23 at 03:17
All you need to do is replace the text 'pop' with 'removeLast' and your code attempt you posted above will work. Just copy and paste it and replace the 'pop' word. – Jake Henry Jan 17 '23 at 17:37
feel free to upvote question also, thanks – mattsmith5 Jun 20 '23 at 17:58

score -1 · Answer 2 · answered Jan 16 '23 at 20:28

public class Solution{
    public static String decodeString(String s) {
        StringBuilder stack = new StringBuilder();
        for(char c : s.toCharArray()) {
            if(c != ']') {
                stack.append(c);
            } else {
                StringBuilder sub_str = new StringBuilder();
                while(stack.charAt(stack.length() - 1) != '[') {
                    sub_str.insert(0, stack.charAt(stack.length() - 1));
                    stack.deleteCharAt(stack.length() - 1);
                }
                stack.deleteCharAt(stack.length() - 1);

                StringBuilder multiplier = new StringBuilder();
                while(stack.length() > 0 && Character.isDigit(stack.charAt(stack.length() - 1))) {
                    multiplier.insert(0, stack.charAt(stack.length() - 1));
                    stack.deleteCharAt(stack.length() - 1);
                }

                for(int i = 0; i < Integer.parseInt(multiplier.toString()); i++) {
                    stack.append(sub_str);
                }
            }
        }
        return stack.toString();
    }

    public static void main(String[] args) {
        System.out.println( decodeString("3[a2[c]]"));
        //Output: "accaccacc"
        System.out.println( decodeString("3[a]2[bc]"));
        //Output: "aaabcbc"
    }

}

Decode String in Java

2 Answers2