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

Author Avatar
清水雅然君 05月 28,2020

题目地址

题目描述

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

编码规则为: 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可以底层使用双向链表实现
15906603401.png
所以,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);
}