每日题解:LeetCode 394. 字符串解码

题目描述

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

编码规则为: 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".

解法

java

  //解析字符串，遇到数字进入栈，遇到[ 进入 遇到] 开始输出
    public String decodeString(String s) {
        char[] sArr= s.toCharArray();
        LinkedList<Integer> stackNum = new LinkedList<>();
        LinkedList<String> stackString = new LinkedList<>();
        int num = 0;
        StringBuffer res=new StringBuffer();
        for (char c : sArr) {
            //获取到数字
            if(Character.isDigit(c)){
                num  = num*10+Integer.parseInt(String.valueOf(c));
            } else if(c=='['){
                //将获取到的数字存入到栈，并且存入之前的字符，开始重写计数
                //stackNum和stackString stackNum[i] stackString[i]记录之前的字符串
                stackNum.add(num);
                stackString.add(res .toString());
                num=0;
                res =new StringBuffer();
            }else if(c==']'){
                StringBuffer temp=new StringBuffer();
                int temp_num=stackNum.removeLast();
                //cc
                for (int i = 0; i < temp_num; i++) {
                    temp.append(res);
                }
                //合并到acc
                res = new StringBuffer(stackString.removeLast() + temp);
            }else if(Character.isLetter(c)){
                res.append(c);
            }

        }
        return res.toString();
    }

C++

public:
    static string decodeString(string s){
        size_t num = 0;
        vector<int> stackNum;
        vector<string> stackString ;
        string res;
        for (int i = 0; i < s.size(); i++) {
            char c=s[i];
            if (isdigit(c)) {
                //用char进行计算时，需要减去48.字符转换为数值
                num=num*10+c - '0';
            }else if(c=='['){
                stackNum.push_back(num);
                stackString.push_back(res);
                num=0;
                res ="";
            }else if(c==']'){
                int count = stackNum.back();
                stackNum.pop_back();
                string resTemp=res;
                for (int k = 1; k < count; k++)
                {
                    resTemp.append(res);
                }
                res = stackString.back() + resTemp;
                stackString.pop_back();
            }else if(isalpha(c)){
            //是否为字母
                res.push_back(c);
            }
        }
        return res;
    }

解题思路

栈

1.分析实例
如果字符串s=3[a2[c]]，输出accaccacc，从这个实例可出，本题是一个按照特定的规则解析字符，如2[c]表示cc，表示两个c的字符缩减，如果存在嵌套，从内到外的顺序解析字符。

3[a2[c]]=> 3[acc]=>accacc 1.1解析内部的2[c]

1.2再解析外部3[acc]

说个题外话，这个规则的解析让我想到了redis的[RESP](https://redis.io/topics/protocol)协议。

*3\r\n
$3\r\n
foo\r\n
$-1\r\n
$3\r\n
bar\r\n

表示 ["foo",nil,"bar"]
2.寻找规则
从走到右读取字符串的字符，如果读到数字，表示我接下来[]内的字符需要重复的次数；读取到[，表示需要接下来的内容是我需要输出的字符，直到读取到]结束。

 s = "3[a]2[bc]", 返回 "aaabcbc".

如果遇到嵌套的[],优先解析最内部的字符，然后逐步从后往前输出。

s = "3[a2[c]]", 返回 "accaccacc"

我们得到规则
2.1从左往右读取规则
2.2最先读取的规则，最后输出
2.3一个完整[]，表示一个输出字段，遇到[开始记录，到]结束。
从第二个规则，得出"后进先出"，符合栈的规则，LIFO。

3.代码实现
3.1 定义两个栈，一个记录数字，一个记录字符
这里我们使用了LinkedList，LinkedList可以底层使用双向链表实现

所以，LinkedList可以表示栈和队列(实现了Deque）

LinkedList<Integer> stackNum = new LinkedList<>();
LinkedList<String> stackString = new LinkedList<>();

定义一个StringBuffer 拼接我们的解析结果

 StringBuffer res=new StringBuffer();

3.1遍历读取字符

char[] sArr= s.toCharArray();
        for (char c : sArr) {
}

读取数字字节

if(Character.isDigit(c)){
num  = num*10+Integer.parseInt(String.valueOf(c));
}

使用Character.isDigit(char c)判断当前的读取中的字节，是不是数字，由于考虑到数字不一定是个位数，可能是十位，百位，所以我们使用一个变量num，每次*10，加上当前的数字
这里我们先把剩余方法的框架写好

//遇到[
else if(c=='['){
//遇到]
}else if(c==']'){
//遇到字符字节
}else if(Character.isLetter(c)){
}

处理字符字节

我们可以使用3[a2[c]]作为我们的解析例子，方便我们理解

遇到`[`

当遇到[,例子中第一个[,不方便理解，我们先将方法空着，直接跳到第二个]，进行解析。
当读取到[，表示我们开始读取[]的字符，这里我们需要初始化之前指针或者临时变量，也可以理解为我们清空上一个读取的数据，把之前的读取的数据存到栈中。

num=0;
res =new StringBuffer();

同时我们需要将上一次读取到的数据存到栈中

 stackNum.add(num);
 stackString.add(res .toString());

遇到`]`

当读取到一个]，我们需要将解析一个N[]
首先我们需要知道重复的个数，读取数字栈顶的元素，可以从上一个读取**遇到[**存入的方式值的，数字栈顶部的元素就是我们读取N[]中数字N。

int temp_num=stackNum.removeLast();

循环拼接我们暂存的字符

StringBuffer temp=new StringBuffer();
for (int i = 0; i < temp_num; i++) {
 temp.append(res);
 }

由于每次遇到[,我们会将res清空，所以res就是N[]中[]之间的字符
合并字符

res = new StringBuffer(stackString.removeLast() + temp);

每次遇到[,我们会将res存到字符栈最后一个元素，字符栈的栈顶元素就是之前的字符

字节

遇到字节拼接到当前res中

else if(Character.isLetter(c)){
res.append(c);
}

清水1024