字符串解码

[编程题]字符串解码

热度指数：3362 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给一个加密过的字符串解码，返回解码后的字符串。

加密方法是：k[c] ，表示中括号中的 c 字符串重复 k 次，例如 3[a] 解码结果是 aaa ，保证输入字符串符合规则。不会出现类似 3a , 3[3] 这样的输入。

数据范围：输出的字符串长度满足 $1 \le n \le 50 \$

示例1

输入

"3[a]"

输出

"aaa"

示例2

输入

"abc"

输出

"abc"

示例3

输入

"3[3[b]]"

输出

"bbbbbbbbb"

算法知识视频讲解

Java

牛客148901号

public String decodeString (String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        StringBuilder result = new StringBuilder();
        StringBuilder numStr = new StringBuilder();
        LinkedList<Integer> numStack = new LinkedList<>();
        LinkedList<StringBuilder> resultStack = new LinkedList<>();
        for (char ch : s.toCharArray()) {
            if (Character.isDigit(ch)) {
                numStr.append(ch);
            } else if (ch == '[') {
                numStack.push(Integer.valueOf(numStr.toString()));
                resultStack.push(result);

                result = new StringBuilder();
                numStr = new StringBuilder();
            } else if (ch == ']') {
                StringBuilder temp = resultStack.pop();
                int num = numStack.pop();
                for (int i = 0; i < num; i++) {
                    temp.append(result);
                }
                result = temp;
            } else {
                result.append(ch);
            }
        }
        return result.toString();
    }

发表于 2024-05-01 23:27:17 回复(0)

Java

JSWAJOB

import java.util.*;


public class Solution {

    public String decodeString (String s) {
        // write code here
        if (s == null || s.length() == 0) return "";
        return process(s.toCharArray(), 0, s.length() - 1);
    }
    private String process(char[] arr, int start, int end ) {
        if(start > arr.length - 1 || end > arr.length - 1) return "";
        StringBuilder ans = new StringBuilder();
        for (int i = start; i <= end; i ++)   {
            if (Character.isDigit(arr[i])) {
                // k[ ? ]
                int idR = findTrueRight(i + 2, arr);
                String ret = process(arr, i + 2, idR - 1);
                //StringBuilder sb = new StringBuilder();
                int k = Integer.parseInt(arr[i] + "");
                for (int w = 0; w < k; w ++) {
                    ans.append(ret);
                }
                i = idR;
            } else {
                ans.append(arr[i]);
            }
        }
        return ans.toString();
    }
    private int findTrueRight(int idx, char[] arr) {
        int countLeft = 1;
        while (true) {
            if (arr[idx] == '[') {
                countLeft ++;
            } else if (arr[idx] == ']') {
                countLeft --;
            }
            if (countLeft == 0) {
                break;
            }
            idx ++;
        }
        return idx;
    }

}

发表于 2024-02-06 15:54:51 回复(0)

Java

blue&&lan

这道面试题我的水平也就这样了

public String decodeString (String s) {
        StringBuilder ss = new StringBuilder();
        StringBuilder sx = new StringBuilder(); 
        Stack<Character> st = new Stack<>();
        String sf="";
        String se="";
        int c=0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='['){
                st.push('[');
            }else if(Character.isDigit(s.charAt(i))){
                st.push(s.charAt(i));
                //c*=Integer.parseInt(String.valueOf(s.charAt(i)));
            }else if(Character.isLetter(s.charAt(i))){
                st.push(s.charAt(i));
            }else if(s.charAt(i)==']'){
                ss.delete(0,ss.length());
                sf="";
                while(st.peek()!='['){
                    sf+=String.valueOf(st.pop());
                }
                st.pop();
                c=Integer.parseInt(String.valueOf(st.pop()));
                int j=0;
                while(j<c){
                    ss.append(sf);
                    j++;
                }
                ss.reverse();
                for(char ch:ss.toString().toCharArray()){
                    st.push(ch);
                }
            }
        }
        while(!st.isEmpty()){
            sx.insert(0,st.pop());
        }
        return sx.toString();
    }

发表于 2022-06-18 17:56:50 回复(0)