2 Java Solutions, 1 using Stack, the other using recursion


  • 0
    M

    Solution 1, stack:

        public String decodeString(String s) {
            if (s == null || s.length() == 0) return "";
            Stack<Character> stack = new Stack<>();
            for (char c : s.toCharArray()) {
                if (c != ']') stack.push(c);
                else {
                    StringBuffer sb = new StringBuffer();
                    while (!stack.isEmpty() && stack.peek() != '[') {
                        sb.append(stack.pop());
                    }
                    if (!stack.isEmpty()) stack.pop();
                    StringBuffer times = new StringBuffer();
                    while (!stack.isEmpty() && Character.isDigit(stack.peek())) {
                        times.insert(0, stack.pop());
                    }
                    int k = Integer.parseInt(times.toString());
                    Stack<Character> temp = new Stack<>();
                    char[] charr = sb.toString().toCharArray();
                    while (k > 0) {
                        for (char ch : charr) temp.push(ch);
                        --k;
                    }
                    while (!temp.isEmpty()) stack.push(temp.pop());
                }
            }
            StringBuffer sb = new StringBuffer();
            while (!stack.isEmpty()) sb.insert(0, stack.pop());
            return sb.toString();
        }
    

    Solution 2, recursion:

        public String decodeString(String s) {
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < s.length(); ++i) {
                char c = s.charAt(i);
                if (Character.isDigit(c)) {
                    int j = i;
                    while (Character.isDigit(s.charAt(j))) ++j;
                    int k = Integer.parseInt(s.substring(i, j));
                    int cnt = 1;
                    i = j + 1;
                    while (cnt > 0 && ++j < s.length()) {
                        if (s.charAt(j) == '[') ++cnt;
                        else if (s.charAt(j) == ']') --cnt;
                    }
                    String word = decodeString(s.substring(i, j));
                    while (k-- > 0) sb.append(word);
                    i = j;
                } else {
                    sb.append(c);
                }
            }
            return sb.toString();
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.