力扣394——字符串解码頭條網

力扣394——字符串解码

2021-03-28 02:59:34 佚名

这道题主要涉及的是对递归和栈的理解。

原题

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例:

<code>s
 = "3[a]2[bc]"
, 返回 "aaabcbc".
s
 = "3[a2[c]]"
, 返回 "accaccacc".
s
 = "2[abc]3[cd]ef"
, 返回 "abcabccdcdcdef"
./<code>

原题url：
https://leetcode-cn.com/problems/decode-string/

解题

递归

这道题目，简单来看就是根据数字和内容，进行不断重复输出，最终得出结果。因此，递归也是最容易让人想到的。

数字代表内容需要重复的次数，[代表一次新的递归开始，]代表本次递归的结束，有点类似括号匹配这种问题。只是需要记录中间结果，以及最开始的s进过一次递归遍历后的下标位置。

基于上面的讲解，我们也就能够写出代码：

<code>
class
 Solution {
    
public
 String decodeString
(String s) {
        StringBuilder resultSb = new StringBuilder();
        dfs(s, 0, resultSb);
        return resultSb.toString();
    }

    
public
 int 
 dfs
(String s, 
int index, StringBuilder resultSb) {
         
        int
 count = 0;
        while (index < s.length()) {
            char temp = s.charAt(index);
             
            if
 (temp >= '0'
 && temp <= '9') {
                count = count * 10
 + temp - '0';
            }
             
            else
 if
 (temp == '[') {
                StringBuilder tempResult = new StringBuilder();
                index = dfs(s, index + 1, tempResult);
                 
                for
 (int
 i = 0; i < count; i++) {
                    resultSb.append(tempResult);
                }
                 
                count = 0;
            }
             
            else
 if
 (temp ==  
']') {
                             
                return index;
            }
             
            else {
                resultSb.append(temp);
            }

            index++;
        }

        return index;
    }
}/<code>

提交OK。

利用栈

既然有递归的写法，那么自然有不递归的写法，这就需要借助栈了。大家可以类比成计算一段普通的数学表达式，里面有括号、数字、符号运算等，所以需要两个栈，分别存储数字和运算符。

这道题目自然也是需要两个栈的，一个用来存储重复的次数，一个用来存储中间的字符串结果。判断出栈、入栈的依据，依据是[]，[代表数字和字符串都压入相应的栈，]代表需要将数字和字符串都需要从栈首压出，进行计算。

接下来看看代码：

<code>
class
 Solution {
    
public
 String decodeString
(String s) 
 {
         
        Stack countStack = new Stack<>();
         
        Stack sbStack = new Stack<>();
         
        StringBuilder tempSb = new StringBuilder();
         
        int
 tempCount = 0;

         
        for
(char temp : s.toCharArray()) {
             
            if
 (temp >= '0'
 && temp <= '9') {
                tempCount = tempCount * 10
 + temp - '0';
            }
             
            else
 if
 (temp == '[') {
                countStack.push(tempCount);
                tempCount = 0;

                sbStack.push(tempSb);
                tempSb = new StringBuilder();
            }
             
            else
 if
 (temp == ']') {
                 
                StringBuilder tempResult = new StringBuilder();
                int count = countStack.pop();
                for
 ( 
int
 j = 0; j < count; j++) {
                    tempResult.append(tempSb);
                }
                 
                StringBuilder sb = sbStack.pop();
                tempSb = sb.append(tempResult);
            }
             
            else {
                tempSb.append(temp);
            }
        }
        
        return tempSb.toString();
    }
}/<code>