LeetCode 394.Decode String

LeetCode新题

LeetCode最近好像又更新了,之前刷了100道左右的Easy和Medium,但是之前刷的题都没有写博客,这次写是因为网上的解法还很少,所以发上来供大家查阅。

LeetCode

后续博客中只会出现比较特殊的算法题,将不再出现其他的题,更多LeetCode Java解法请到我的GitHub,里面会有翻译和Solution

题意和解法

这道题的题意其实很简单,就不过多解释了,看到此类表达式的计算,我们第一个想到的数据结构就是,利用栈的先进后出性质进行计算。

过程

遍历字符串,遇到数字、字母和[直接进栈,遇到],然后出栈,先找出所有字母,直到[(也要出栈),然后再继续出栈找出数字,这里注意数字可能是多位的,比如123[a],所以出栈的终止条件是栈空或者遇到非数字的字符,通过上面出栈的字符串和数字,组成新的字符串,如字符串2[ab],新的字符串应该为abab,这些新的字符也必须再重新进栈。就这么简单~

AC代码

第一版代码,后面如果优化了会再更新

public static String decodeString(String s) {
    if (s == null || s.length() == 0)
        return s;
    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()) {
        if (c == ']') {
            StringBuilder sb = new StringBuilder();
            while (!stack.isEmpty() && ((stack.peek() >= 'a' && stack.peek() <= 'z') || stack.peek() == '[')) {
                char ccc = stack.pop();
                if (ccc == '[')
                    break;
                sb.insert(0, ccc);
            }
            if (stack.isEmpty()) {
                return sb.toString();
            } else {
                int count = 0;
                int w = 1;
                while (!stack.isEmpty() && stack.peek() >= '0' && stack.peek() <= '9') {
                    int val = stack.pop() - '0';
                    count += val * w;
                    w *= 10;
                }
                char[] chars = sb.toString().toCharArray();
                while (count > 0) {
                    for (char cc : chars)
                        stack.push(cc);
                    count--;
                }
            }
        } else
            stack.push(c);
    }
    StringBuilder sb = new StringBuilder();
    while (!stack.isEmpty())
        sb.insert(0, stack.pop());
    return sb.toString();
}
坚持原创分享,您的支持将鼓励我不断前行!