首页 > 其他 > 详细

Decode String

时间:2019-12-21 15:40:42      阅读:75      评论:0      收藏:0      [点我收藏+]
public class Solution {
    /**
     * @param s: an expression includes numbers, letters and brackets
     * @return: a string
     */
    public String expressionExpand(String s) {
        Stack<Object> stack = new Stack<>();
        int num = 0;
        
        for (char c: s.toCharArray()) {
            if (Character.isDigit(c)) {
                num = num * 10 + c - ‘0‘;
            } else if (c == ‘[‘) {
                stack.push(Integer.valueOf(num));
                num = 0;
            } else if (c == ‘]‘) {
                String newStr = popStack(stack);
                Integer count = (Integer) stack.pop();
                for (int i = 0; i < count; i++) {
                    stack.push(newStr);
                }
            } else {
                stack.push(String.valueOf(c));
            }
            
        }
        return popStack(stack);
    }
    
    private String popStack(Stack<Object> stack) {
        // pop stack until stack is empty or get a number
        Stack<String> buffer = new Stack<>();
        while (!stack.isEmpty() && (stack.peek() instanceof String)) {
            buffer.push((String) stack.pop());
        }
        
        StringBuilder sb = new StringBuilder();
        while (!buffer.isEmpty()) {
            sb.append(buffer.pop());
        }
        return sb.toString();
    }
}

  

Description

Given an expression s contains numbers, letters and brackets. Number represents the number of repetitions inside the brackets(can be a string or another expression).Please expand expression to be a string.

Numbers can only appear in front of “[]”.

Example

Example1

Input: S = abc3[a]
Output: "abcaaa"

Example2

Input: S = 3[2[ad]3[pf]]xyz
Output: "adadpfpfpfadadpfpfpfadadpfpfpfxyz"

思路:递归实现 or 非递归实现。
   对于非递归实现,使用栈来解决。遇见“【“将数字放入栈中,遇见“】”将栈中的字符弹出,直到栈为空,或遇见数字,当遇见的是普通的字符,直接放入栈中。

 

 
 

Decode String

原文:https://www.cnblogs.com/FLAGyuri/p/12076969.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!