力扣LeetCode 394题：字符串解码（栈，递归）

分手后的思念是犯贱 2023-02-13 14:35 3阅读 0赞

题目：

> 给定一个经过编码的字符串，返回它解码后的字符串。  
> 编码规则为: k\[encoded\_string\]，表示其中方括号内部的 encoded\_string 正好重复 k 次。注意 k 保证为正整数。  
>   
> **你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。**  
> 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2\[4\] 的输入。

> 示例:  
> s = “3\[a\]2\[bc\]”, 返回 “aaabcbc”.  
> s = “3\[a2\[c\]\]”, 返回 “accaccacc”.  
> s = “2\[abc\]3\[cd\]ef”, 返回 “abcabccdcdcdef”.

### 一、栈操作 ###

因为有左右括号，中间字符需要重复多少次这样的情况，且给出的例子已经表明，这个题目显然存在括号嵌套。所以很容易想到需要用栈。

我们捋一捋思路，以第二个例子出发：

##### s = " 3 \[ a 2 \[ c \] \] " #####

*  1.数字3，需要入栈；Stack=3
 *  2.左括号，需要入栈；Stack=3\[
 *  3.字符a，需要入栈；Stack=3\[a
 *  4.数字2，需要入栈；Stack=3\[a2
 *  5.左括号，需要入栈；Stack=3\[a2\[
 *  6.字符c，需要入栈；Stack=3\[a2\[c
 *  7. 右括号，遇到右括号，则需要出栈。一直出到遇到左括号为止，这就是一个完整的括号里的需要重复的字符串内容了，结果是 c ；Stack=3\[a2  
    .继续出栈，这时候出来的一定是数字，代表这一段需要重复的次数。我们取出数字 2 ，将上一步取出的字符串进行重复得到 cc 。Stack=3\[a  
    将已经重复好的字符串再次入栈。因为只要没结束，就说明这一段是内嵌的，那么更外围的数字，重复的内容肯定包含里面的内容。Stack=3\[acc
 *   8.右括号，遇到右括号，出栈。出到遇到左括号为止，结果是acc；Stack=3  
    继续出栈，出来的是数字3，代表需要重复的次数。取出3重复字符串得到accaccacc；Stack=空  
    将已经重复好的字符串再次入栈。Stack=accaccacc
 *  9.此时原字符串已经遍历完了，我们直接可以从栈里取出结果**accaccacc。**

#### 总结一下步骤： ####

1.  **数字。解析完入栈。（这是因为数字可能出现多位数，因此应该解析出一个完整的数字之后再入栈）**
2.  **左括号，入栈；**
3.  **字符，入栈；**
4.  **右括号，开始出栈，一直出到出来左括号。下一个出来的就是数字，用数字和出来的字符串进行重复之后，再入栈。（由于字符出来的是逆序，需要进行翻转）**
5.  **继续遍历原字符串，重复以上过程。**

以下是按照直接思路，用ArrayList模拟一个栈写出的代码。

class Solution {
        
        public String decodeString(String s) {
        
            StringBuilder ans=new StringBuilder();
            List<String> list=new ArrayList<>();
            int i=0;
            int count=0;
            //遍历整个s的操作
            while(i<s.length()){
        
                char c=s.charAt(i);
                //对于数字，先解析，再入栈
                if(c>='0'&&c<='9'){
        
                    count=count*10+(c-'0');
                    i++;
                }else if('['==c||c>='a' && c<='z' || c >='A' && c<='Z'){
        
                    if(count!=0){
        
                        list.add(Integer.toString(count));
                        count=0;
                    }
                    list.add(String.valueOf(c));
                    i++;
                }else{
        
                    //(c==']'),初始化循环结果
                    StringBuilder sb=new StringBuilder();
                    //出栈准备
                    int outPtr=list.size()-1;
                    //直到出现前括号为止
                    while(!(list.get(outPtr).equals("["))){
        
                        sb.insert(0,list.get(outPtr));
                        list.remove(outPtr);
                        outPtr--;
                    }
                    //此时的outPtr指向的是[,删除
                    list.remove(outPtr--);
                    //获取下一个，也就是数字
                    int repeatNum=Integer.parseInt(list.get(outPtr));
                    //然后数字也删除，并重新入栈
                    list.remove(outPtr);
                                        
                    for(int j=0;j<repeatNum;j++){
        
                        list.add(sb.toString());
                    }
                    i++;
                }
            }
            //当整个遍历完之后，重新存入list的就是一个完整的结果，只需要再读取出来就可以
            for(int j=0;j<list.size();j++){
        
                ans.append(list.get(j));
            }
            return ans.toString();
        }
    }

其中，获取完整数字本来应该用while进行，但是不想破坏if-else语句。  
观察到每一次出栈数字的下一个总是前括号，只需在遇到前括号的时候把count结果压入栈，同时再把count清零即可。

LeetCode评论里有用LinkedList，然后用了一些内部方法，会比这个更简洁一些。我自己的这个方法好处在于更偏向于顺序进行的过程。

以下是采用LinkedList的代码，同时用了两个栈保存数字和字符串。

class Solution {
        
        public String decodeString(String s) {
        
            StringBuilder ans = new StringBuilder();//结果
            int count = 0;
    
            //把字符和数字存入两个不同的栈
            LinkedList<Integer> countStack = new LinkedList<>();
            LinkedList<String> ansStack = new LinkedList<>();
    
            for(Character c : s.toCharArray()) {
        
                if(c >= '0' && c <= '9'){
        
                    count = count * 10 + Integer.parseInt(c + "");
                }else if(c == '[') {
        
                    countStack.addLast(count);
                    ansStack.addLast(ans.toString());
                    count = 0;//count重新置零
                    ans = new StringBuilder();//此段字符串也清零
                }else if(c == ']') {
        
                    //如果遇到右括号，该出栈，出一个数字
                    //同时用ans保存最后面的字符，重复之后，再出栈前面的字符，再重复
                    //注意ans是全局变量，保证了答案完整
                    StringBuilder tmp = new StringBuilder();
                    int curCount = countStack.removeLast();
                    for(int i = 0; i < curCount; i++){
        
                        tmp.append(ans);
                    }
                    ans = new StringBuilder(ansStack.removeLast() + tmp);
                }else{
        
                    ans.append(c);//如果遇到字符，就入栈，
                }
            }
            return ans.toString();
        }
    }

### 二、递归 ###

一般来说，可以用栈解决的问题也能很容易联想到递归，但是这个题写起来并不容易。（我写了一下午没写出来，最后去抄答案，路漫漫啊）

递归的思路就是这样的，这个递归方法是为了解析字符串：

1.  如果遇到了数字，那获取到完整的count，接着要把后面的字符串进行解析，然后重复count次，也就是调用本身进行递归；
2.  如果遇到的是字符，那么就加上去，然后返回给上一级让他去重复count次；
3.  如果遇到的是前括号，什么也不用做，继续游走就可以；
4.  如果遇到的是后括号，返回，因为这一层递归没有任何字符串的收益。

class Solution {
        
        String src;
        int ptr;
    
        public String decodeString(String s) {
        
            src = s;
            ptr = 0;//指针
            return getString();//调用递归方法
        }
    
        public String getString() {
        
            if (ptr == src.length() || src.charAt(ptr) == ']') {
        
                return "";
            }
    
            char cur = src.charAt(ptr);//
            int count = 1;
            String ret = "";
    
            if (Character.isDigit(cur)) {
        
                // 解析数字
                count = getDigits();
                // 过滤左括号
                ++ptr;
                // 解析 String，这里，在左括号和右括号中间就开始递归。
                String str = getString();
                // 过滤右括号
                ++ptr;
                //接着把处理好的子字符串进行拼接
                while (count-- > 0) {
        
                    ret += str;
                }
            } else if (Character.isLetter(cur)) {
        
                // 解析 Char
                ret = String.valueOf(src.charAt(ptr++));
            }
            
            //最后返回
            return ret + getString();
        }
    
        //解析数字的方法
        public int getDigits() {
        
            int ret = 0;
            while (ptr < src.length() && Character.isDigit(src.charAt(ptr))) {
        
                ret = ret * 10 + src.charAt(ptr++) - '0';
            }
            return ret;
        }
    }

这里面因为几个方法都是单独的，为了避免传参的麻烦，直接把原始字符串复制了一个src字符串。

加油，我可以，我能行