leetcode [#394]

目录

• 1. 题目
• 2. 解决方案
• 3. 注意事项

题目

Given an encoded string, return it’s 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; 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 won’t be input like 3a or 2[4].

Example:
s = “3[a]2[bc]”, return “aaabcbc”.
s = “3[a2[c]]”, return “accaccacc”.
s = “2[abc]3[cd]ef”, return “abcabccdcdcdef”.

---

解决方案

public class Solution {
    public String decodeString(String s) {
        if(s.length() == 0 || s.indexOf("[") == -1) return s;
        
        Stack<Integer> kStack = new Stack<>();
        Stack<String> strStack = new Stack<>();
        String lastSec = s.substring(s.lastIndexOf(']') + 1);
        String firstSec = "";
        String lastBracket = "";
        int lastCharIndex = -1;
        Boolean firstNotLetter = false;
        int firstNotLetterIndex = -1;
        StringBuilder res = new StringBuilder();
        
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) >= 'a' && s.charAt(i) <= 'z'){
                lastCharIndex = i;
            } else if(s.charAt(i) == '['){
                String tmpNum = s.substring(lastCharIndex + 1, i);
                kStack.push(Integer.valueOf(tmpNum));
                int m = i + 1;
                while(s.charAt(m) >= 'a' && s.charAt(m) <= 'z') m++;
                String tmpStr = s.substring(i + 1, m);
                strStack.push(tmpStr);
                lastCharIndex = i;
                lastBracket = "[";
            } else if(s.charAt(i) == ']'){
                StringBuilder x = new StringBuilder();
                String topStr = strStack.pop();
                Integer topNum = kStack.pop();
                if(lastBracket.equals("[")){
                    for(int k = 0; k < topNum; k++) x.append(topStr);
                    res = res.append(x);
                } else {
                    StringBuilder tmp = new StringBuilder();
                    tmp.append(topStr);
                    tmp.append(res);
                    for(int k = 0; k < topNum; k++) x.append(tmp);
                    res = x;
                }
                int m = i+1;
                while (m < s.length() && s.charAt(m) >= 'a' && s.charAt(m) <= 'z'){
                    res = res.append(s.charAt(m));
                    m++;
                }
                if(m == s.length()) lastSec = "";
                lastCharIndex = i;
                lastBracket = "]";
            } else {
                if(firstNotLetter == false){
                    firstNotLetterIndex = i;
                    firstNotLetter = true;
                }
            }
        }
        firstSec = s.substring(0, firstNotLetterIndex);
        return firstSec + res.toString() + lastSec;
    }
}

---

注意事项

1. 先考虑特殊情况，对于长度为零的或者没有方括号的输入字符串，直接返回。
2. 需要两个栈，一个保存倍数K，一个保存字符串片段。
3. firstSec表示第一个字符串片段（不包含数字，方括号），这部分作为结果的开头部分直接返回。firstNotLetter标志位就是用于找到第一个不为数字的地方，从而firstNotLetterIndex就是其对应的下标，截取后可得到firstSec。
4. lastBracket表示上一个方括号是左括号还是右括号，用于判断是嵌套方括号还是并列方括号。
5. lastCharIndex表示最近遇到的字母的下标，用于做字符串截取从而获得K值（具体意义见遍历过程）
6. 遍历字符串：
   6.1 如果遇到字母，更新lastCharIndex即可；
   6.2 如果遇到左方括号：
   　　6.2.1 截取左方括号左边的紧邻的数字字符串片段，压入kStack，作为K值；
   　　6.2.2 截取左方括号右边的紧邻的字母字符串片段，压入strStack，作为str值；
   　　6.2.3 更新lastCharIndex，指向当前下标；
   　　6.2.4 更新lastBracket，为”[“。
   6.3 如果遇到右方括号：
   　　6.3.1 strStack弹出一个元素topStr，kStack弹出一个元素topNum
   　　6.3.2 根据lastBracket的情况，决定是否拼接上当前结果res再进行倍增（即考虑是否有括号嵌套的问题）
   　　　　6.3.2.1 如果lastBracket是”[“，说明当前右方括号内部不是嵌套的，因此直接将topStr倍乘topNum次即可；
   　　　　6.3.2.2 如果lastBracket是”]”，说明当前右方括号内部有嵌套的，因此需要将topStr和当前res结合在一起进行倍乘
   　　6.3.3 处理完倍乘后，考虑右方括号右面可能存在的字母（无数字k，即单倍的），这些显然也有拼接进res中；
   　　6.3.4 更新lastBracket，为”]”。
   6.4 对于遇到的第一个数字字符，要根据其下标决定firstSec的内容。
   6.5 最后，将firstSec和res拼接在一起返回，即为最后的结果。