首页 > 试题广场 >

字符串解码

[编程题]字符串解码

热度指数：3311 时间限制：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

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)

牛客658532137号

不止一次吐槽牛客网题目的描述水准，要么题说不清楚，要么给的测试样例不够多。本来题目就说的不算清楚，测试样例给的少，谁知道你出题人心里还有另一种想法啊

发表于 2023-07-11 23:02:47 回复(0)

冲啊啊123

public String decodeString (String s) {
        // write code here
        Stack<String> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == ']') {
                String temp = "";
                while (!"[".equals(stack.peek())) {
                    temp = stack.pop() + temp;
                }
                stack.pop();
                stack.push(process(temp, Integer.valueOf(stack.pop())));
            } else {
                stack.push(String.valueOf(c));
            }
        }
        String res = "";
        while (!stack.isEmpty()) {
            res = stack.pop() + res;
        }
        return res;
    }
    public String process(String str, int cnt) {
        String res = "";
        while (cnt > 0) {
            res = res + str;
            cnt--;
        }
        return res;
    }

发表于 2022-10-31 21:22:39 回复(0)

Python 3

牛客631265075号

class Solution:
    def decodeString(self, s: str) -> str:
        # write code here
        stack = []
        for i in s:
            if i != ']':
                stack.append(i)
            else:
                k = 0
                c = ''
                while len(stack) > 0:
                    ip = stack.pop()
                    if ip == '[':
                        k = int(stack.pop())
                        break
                    else:
                        c = ip + c
                res = ''
                if k > 0:
                    for j in range(0, k):
                        res = res + c
                else:
                    res = c
                stack.append(res)
        rr = ''
        while len(stack) > 0:
            rr = stack.pop()+rr
        return rr

发表于 2022-08-23 16:19:22 回复(0)

JavaScript Node

勒布_朗詹姆斯

    let res = [];

    for (let i = 0; i < s.length; ++i){
        if (s[i] !== ']'){
            res.push(s[i])
        } else{
            let tmp = [];
            let num = [];
            while(res.length){
                let cur = res.pop();
                if (cur !== '['){
                    tmp.unshift(cur);
                } else{

                    while(res.length){
                        let item = res.pop();
                        if (!isNaN(item)){
                            num.unshift(Number(item));
                        } else{
                            res.push(item);
                            break;
                        }
                    }
                    break;
                }
            }
            let store = tmp.join('').repeat(num.join('')).split('');
            res.push(...store);
        }    
    }
    return res.join('');

发表于 2022-08-01 12:10:37 回复(0)

JavaScript Node

CoolTian

function decodeString( s ) {
    let numStack = [],strStack = [],res = '',num = 0;
    for (let str of s) {
        if (!isNaN(str)) {
            num = num*10+parseInt(str);
          console.log(num)
        } else if (str === '[') {
            strStack.push(res);
            numStack.push(num);
            res = '';
            num = 0;
        } else if (str === ']') {
            res = strStack.pop() + res.repeat(numStack.pop());
        } else {
            res += str;
        }
    }
    return res;
}

发表于 2022-07-24 01:49:53 回复(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)

菲尼克斯弗兰克

import java.util.*;
// 使用栈处理，遇到闭合就复制k份
public class Solution {
    public String decodeString (String s) {
        ArrayDeque<Character> stack = new ArrayDeque<>();
        StringBuilder res = new StringBuilder(),str = new StringBuilder();
        int num = 0;
        for (char c : s.toCharArray()) {
            if (c == ']') {
                if (str.length() > 0) str.delete(0, str.length());
                while (stack.peek() != '[') {
                    str.insert(0, stack.pop());
                }
                stack.pop(); // 扔出去[
                num = stack.pop()-'0';
                for (int j = 0; j < num; j++) {
                    for (int k = 0; k < str.length(); k++) {
                        stack.push(str.charAt(k));
                    }
                }
            } else stack.push(c);
        }
        while (!stack.isEmpty()) {
            res.insert(0, stack.pop());
        }
        return res.toString();
    }
}

发表于 2022-01-26 15:29:08 回复(0)

JavaScript Node

牛客300673134号

function decodeString( s ) {
    // stack用来存储数字，leftBraceNum表示左括号数量
    let stack = [],leftBraceNum = 0,res = '';
    for(let i = 0; i < s.length; i++) {
        if(s[i] === '[') {
            leftBraceNum++;
            let maxleftBraceNum = 1;
            let str = s[i];
           while(leftBraceNum !== 0) {
               i++;
               if(s[i] === '[') {
                   leftBraceNum++;
                   maxleftBraceNum++;
               }
               if(s[i] === ']') {
                   leftBraceNum--;
               }
               str += s[i];
           }
           
           if(maxleftBraceNum > 1) {
               //递归解析字符串
                str = str.substring(1, str.length - 1);
                str = decodeString(str);
           }else {
                //计算
                str = str.substring(1, str.length - 1);
           }
            
            let n = stack.pop();
            while( n > 0) {
                res += str;
                n--;
            };
        }else if(!isNaN(s[i])){
            //数字
            stack.push(Number(s[i]));
        }else {
            res+=s[i];
        }
    }
    return res;
}

发表于 2021-11-18 00:43:46 回复(0)