🌕 394. 字符串解码

难度: 🌕

问题描述

---

解法 1 - 栈

class Solution {
    public String decodeString(String s) {
        // 思路：
        // 栈
        int len = s.length();
        LinkedList<String> stack = new LinkedList<>();
        int index = 0;
        while(index < len) {
            char c = s.charAt(index);
            if(c >= '0' && c <= '9') {
                int j = index + 1;
                while(j < len && s.charAt(j) >= '0' && s.charAt(j) <= '9') {
                    j ++;
                }
                String num = s.substring(index, j);
                stack.push(num);
                index = j;
            } else if(c >= 'a' && c <= 'z') {
                int j = index + 1;
                while(j < len && s.charAt(j) >= 'a' && s.charAt(j) <= 'z') {
                    j ++;
                }
                String str = s.substring(index, j);
                stack.push(str);
                index = j;
            } else if(c == '[') {
                stack.push("[");
                index ++;
            } else if(c == ']') {
                // 弹栈 - 直到遇到对应的左括号
                // 此过程中如果遇到多个字符串，尽可能拼接
                StringBuilder sb = new StringBuilder();
                while(!stack.isEmpty() && !stack.peek().equals("[")) {
                    String cur = stack.pop();
                    sb.insert(0, cur);
                }
                String sin = sb.toString(); // 单个字符串
                stack.pop(); // 弹出左括号
                String num = stack.pop(); // 弹出数字
                int tmp = Integer.valueOf(num);
                sb = new StringBuilder();
                for(int i = 0; i < tmp; i ++) {
                    sb.append(sin);
                }
                // 压栈当前字符串
                stack.push(sb.toString());
                index ++;
            }
        }
        StringBuilder res = new StringBuilder();
        while(!stack.isEmpty()) {
            String cur = stack.pop();
            res.insert(0, cur);
        }
        return res.toString();
    }

---

输出 1

---

解法 2 - 递归

class Solution {
    int len;
    public String decodeString(String s) {
        // 思路：
        // 递归
        len = s.length();
        return mySol(s, 0, len - 1);
    }

    private String mySol(String str, int left, int right) {
        // 递归终止条件
        if(left > right || left >= len) {
            return "";
        }
        // System.out.println(left + ":" + right + str.substring(left, right + 1));
        StringBuilder sb = new StringBuilder();
        char c = str.charAt(left);
        if(c >= '0' && c <= '9') {
            // 数字
            int j = left + 1;
            while(j < len && str.charAt(j) >= '0' && str.charAt(j) <= '9') {
                j ++;
            }
            int num = getNum(str, left, j - 1);
            // 数字后面跟着的肯定是左括号，需要找到对应的右括号进行切分
            // 当左右括号相等时，说明找到了对应的右括号
            int i = j; // 指向左括号
            j ++; // j 原本肯定指向 '['
            int count = 1; // 已经有了一个左括号
            while(j < len && count != 0) {
                if(str.charAt(j) == '[') {
                    count ++;
                }
                if(str.charAt(j) == ']') {
                    count --;
                }
                if(count == 0) {
                    break;
                } else {
                    j ++;
                }
            }
            String cur = mySol(str, i, j); // j 对应右括号
            for(int k = 0; k < num; k ++) {
                sb.append(cur);
            }
            String next = mySol(str, j + 1, right); // j 后面的部分肯定是完整的，因此得到
            sb.append(next);
        } else if(c >= 'a' && c <= 'z') {
            // 是字符串
            int j = left + 1;
            while(j < len && str.charAt(j) >= 'a' && str.charAt(j) <= 'z') {
                j ++;
            }
            String prev = str.substring(left, j);
            if(j >= len) {
                // 只有一个字符串，返回
                return prev;
            }
            // 后面还有元素，只能是数字，递归
            String next = mySol(str, j, right);
            sb.append(prev).append(next);
        } else if(c == '[') {
            // 右括号肯定在最右边，去掉这层包装
            String cur = mySol(str, left + 1, right - 1);
            sb.append(cur);
        }
        // System.out.println("     " + sb.toString());
        return sb.toString();
    }

    private int getNum(String str, int left, int right) {
        int res = 0;
        for(int i = left; i <= right; i ++) {
            char c = str.charAt(i);
            int cur = c - '0';
            res = res * 10 + cur;
        }
        return res;
    }
}

---

输出 2