【leetcode】第394题：字符串解码（华为笔试题）

我不是女神ヾ 2022-02-20 12:55 461阅读 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".

*  分析：两个栈：一个栈用来存储目标字符串，一个栈用来存储数字。遍历输入的字符串，用res记录遇到 '\[’ 之前的字符，curNum记录遇到 ‘\[’ 之前的数字，当遇到 '\[' 时，将 res 和 curNum 全都压栈，然后设置为初始值（方便下次再遇到 ‘\[’ 时使用）。当遇到 ‘\]’ 时开始拼接括号里的字符串到 res 中。
 *  代码实现：

public class DecodeString_394 {
    
        public static String decodeString(String str){
            String res = "";
    
            // 记录'['之前的数字
            Stack<Integer> countStack = new Stack<>();
            // 记录'['之前的字符串运算结果
            Stack<String> resStack = new Stack<>();
    
            int index = 0;
            int curNum = 0;
    
            while(index < str.length()){
                char ch = str.charAt(index);
                if(Character.isDigit(ch)){
                    // 如果当前字符是数字的时候，计算出来括号中的数字
                    while(Character.isDigit(str.charAt(index))){
                        curNum = 10 * curNum + (str.charAt(index++) - '0');
                    }
                }else if(ch == '['){
                    // 遇到 '[' 时，将之前的字符和数字都压栈，并将其引用设为初始值
                    resStack.push(res);
                    res = "";
                    countStack.push(curNum);
                    curNum = 0;
                    index++;
                }else if(ch == ']'){
                    // 遇到 ']' 就将两个栈里面的内容弹出，拼接到 res 中
                    StringBuilder temp = new StringBuilder(resStack.pop());
                    int repeatTimes = countStack.pop();
                    for (int i = 0; i < repeatTimes; i++) {
                        temp.append(res);
                    }
                    res = temp.toString();
                    index++;
                }else{
                    // index 位置处的字符为字母，直接添加到res中，index++
                    res += str.charAt(index++);
                }
            }
            return res;
        }
    }

> 华为笔试题：
> 
> 题目：给定一个字符串，字符串包括数字、大小写字母以及括号（包括大括号、中括号、小括号），括号可以嵌套，即括号里面可以出现数字和括号。按照如下的规则对字符串进行展开，不需要考虑括号成对不匹配问题。用例保证括号匹配，同时用例保证每个数字后面都有括号，不用考虑数字后面没有括号的这种情况，即 2aa(b) 这种情况不用考虑。
> 
> 1、数字表示括号里的字符串重复的次数，展开后的字符串不包含括号；
> 
> 2、将字符串进行逆序展开。
> 
> 输出最终展开的字符串。

*  与上面的题相比：只有两点变化：1、多种括号；2、逆序输出。
 *  1、首先将输入的字符串中的三种括号处理成一种；
 *  2、将解码后的字符串转成StringBuffer，利用StringBuffer的 reverse方法，直接逆序输出即可。

public class Second {
    
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            String str = sc.nextLine();
    
            if(str == null || str.length() < 1){
                System.out.println("");
            }
            // 将所有的括号都替换成（）形式
            String newStr = replaceStr(str);
            // 解码字符串
            String resString = decodeString(newStr);
            // 逆序字符串
            StringBuffer sb = new StringBuffer(resString);
            System.out.print(sb.reverse());
        }
    
        public static String replaceStr(String str){
            str = str.replace('{','(');
            str = str.replace('[','(');
            str = str.replace('}',')');
            str = str.replace(']',')');
    
            return str;
        }
    
        public static String decodeString(String str){
            String res = "";
    
            // 记录'['之前的数字
            Stack<Integer> countStack = new Stack<>();
            // 记录'['之前的字符串运算结果
            Stack<String> resStack = new Stack<>();
    
            int index = 0;
            int curNum = 0;
    
            while(index < str.length()){
                char ch = str.charAt(index);
                if(Character.isDigit(ch)){
                    // 如果当前字符是数字的时候，计算出来括号中的数字
                    while(Character.isDigit(str.charAt(index))){
                        curNum = 10 * curNum + (str.charAt(index++) - '0');
                    }
                }else if(ch == '('){
                    // 遇到 '[' 时，将之前的字符和数字都压栈，并将其引用设为初始值
                    resStack.push(res);
                    res = "";
                    countStack.push(curNum);
                    curNum = 0;
                    index++;
                }else if(ch == ')'){
                    // 遇到 ']' 就将两个栈里面的内容弹出，拼接到 res 中
                    StringBuilder temp = new StringBuilder(resStack.pop());
                    int repeatTimes = countStack.pop();
                    for (int i = 0; i < repeatTimes; i++) {
                        temp.append(res);
                    }
                    res = temp.toString();
                    index++;
                }else{
                    // index 位置处的字符为字母，直接添加到res中，index++
                    res += str.charAt(index++);
                }
            }
            return res;
        }
    }