【Day 4 】2022-11-04 - 394. 字符串解码

[azl397985856]

394. 字符串解码

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/decode-string/

前置知识

• 栈
• 括号匹配

  题目描述

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

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

 

示例 1：

输入：s = "3[a]2[bc]" 输出："aaabcbc" 示例 2：

输入：s = "3[a2[c]]" 输出："accaccacc" 示例 3：

输入：s = "2[abc]3[cd]ef" 输出："abcabccdcdcdef" 示例 4：

输入：s = "abc3[cd]xyz" 输出："abccdcdcdxyz"

[ruikiwi]

Idea

Stack

Code

class Solution(object):
    def decodeString(self, s):
        stack = []; curNum = 0; curString = ''
        for c in s:
            if c == '[':
                stack.append(curString)
                stack.append(curNum)
                curString = ''
                curNum = 0
            elif c == ']':
                num = stack.pop()
                prevString = stack.pop()
                curString = prevString + num*curString
            elif c.isdigit():
                curNum = curNum*10 + int(c)
            else:
                curString += c
        return curString

[zrtch]

/**
 * @param {string} s
 * @return {string}
 */
var decodeString = function(s) {
    let r = ''
    var a = function(t) {
        const firstClose = t.indexOf(']')
        if ( firstClose == -1 ) r = t 
        if ( firstClose != -1 ) {
        const rangeLastOpen =  t.substring(0, firstClose).lastIndexOf('[')
        var reg = /(\d+)$/g
        var z = reg.exec(t.substring(0, rangeLastOpen))
        if (z) {
        const zNum = z[0]
        const changeChars = t.substring(rangeLastOpen + 1, firstClose)
        const num = parseInt(zNum)
        let beforechange = ''
        for(let a = 0; a < num ; a ++) {
            beforechange += changeChars
        }
        const result = t.substring(0, rangeLastOpen - zNum.length) + beforechange + t.substring(firstClose + 1)
        if (result.indexOf(']') != -1) a(result)
        if (result.indexOf(']') === -1) r = result
        }
        }
    }
    a(s)
    return r;
};

[paopaohua]

思路

字符串 + 栈

代码

class Solution {
    public String decodeString(String s) {
        Stack<Character> stack = new Stack<>();
        // 遍历字符串（转char字符串）
        for(char c : s.toCharArray()){
            if(c != ']'){ // 没到最后就一直向栈中压
                stack.push(c);
            }else{
                // 数组中的数已经全部进栈，取出字符串
                StringBuilder sb = new  StringBuilder();
                // 看栈中是不是字母
                while(!stack.isEmpty() && Character.isLetter(stack.peek()))
                    sb.insert(0,stack.pop());

                String s1 = sb.toString();
                stack.pop(); // 此时栈中就剩下一个‘[’,弹出

                // 获取倍数
                while(!stack.isEmpty() && Character.isDigit(stack.peek())){
                     sb.insert(0,stack.pop());
                }

               int count = Integer.valueOf(sb.toString());  // 倍数

                // 将倍数 x 字符
                while(count  > 0 ){
                    for(char c1 : s1.toCharArray()){
                        stack.push(c1);
                    }
                    count--;
                    }
                }
        }
        // 将栈中数据取出
        StringBuilder res = new StringBuilder();
        while(!stack.isEmpty())
            res.insert(0,stack.pop());
        return res.toString();
    }
}

复杂度

• 时间 o(n)
• 空间 o(n)

[tiandao043]

思路

模拟，第一次想错了，用一个栈装数一个栈装字母，结果处理不了嵌套后两个右半括号之间有字母的情况，一直企图缝缝补补，发现得记录数字和字母是否在同一级，企图每个栈里面加pair 的 int 修补。 后看了题解，其实将数字和字母装进同一格即可，理论上pair修补也行，但不是正道。 递归也可以做（编译原理）题解版本。

代码 (误）

class Solution {
public:
    string decodeString(string s) {
        string ans;
        int l=0,r=0;
        int ls=0,rs=0;
        vector<pair<int,int>> num;
        vector<pair<int,string>> str;
        int endnum=-1;
        int cnt=0;
        int flag=-1; // -1初始，1 num，2 alpha,[ 3,] 4
        for(int i=0;i<s.length();i++){
            if(num.empty()&&isalpha(s[i])){
                ans+=s[i];
            }
            if(isdigit(s[i])){
                if(flag!=1){
                    if(flag==2){                        
                        rs=i;
                        pair <int,string> pi;
                        pi.first=cnt;
                        pi.second=s.substr(ls,rs-ls);                        
                        str.push_back(pi);
                    }
                    l=i;
                    // cout<<l<<endl;
                    flag=1;
                }      
            }else if(isalpha(s[i])){
                if(flag!=2){                    
                    ls=i;
                    flag=2;
                }
            }else if(s[i]=='['){
                r=i;
                int ss=stoi(s.substr(l,r-l)); 
                pair<int,int> pp;
                pp.first=cnt;
                pp.second=ss;               
                num.push_back(pp);
                cnt++;                
                ls=i+1;
                flag=3;
            }else if(s[i]==']'){ 
                cnt--;               
                endnum=i;      
                rs=i;
                pair <int,int> ti;                
                ti=num.back(); 
                int time=ti.second;              
                num.pop_back();                    
                if(!num.empty()){
                    if(flag==4){                        
                        string aa;
                        string sstr=str.back().second;
                        // str.pop_back();
                        for(int j=0;j<time;j++){                    
                            aa+=sstr;
                        }
                        string te=str.back().second;
                        int tt=str.back().first;
                        str.pop_back();
                        cout<<te+aa<<endl;

                        pair <int,string> ppp;
                        ppp.first=cnt;
                        ppp.second=te+aa;
                        str.push_back(ppp);
                        ls=i+1;
                    }else{

                        string ss=s.substr(ls,rs-ls);                        
                        string aa;
                        // str.pop_back();

                        for(int j=0;j<time;j++){                    
                            aa+=ss;
                        }
                        // cout<<aa<<endl;
                        string te=str.back().second;
                        int ttt=str.back().first;
                        str.pop_back();
                        pair <int,string> ppp;
                        ppp.first=ttt;
                        ppp.second=te+aa;
                        str.push_back(ppp);
                    }
                }
                else{
                    cout<<"!!!!"<<i<<endl;                   
                    if(flag==4){
                        string acc=str.back().second;
                        int tt=str.back().first;
                        str.pop_back();
                        string str1;
                        for(int j=0;j<time;j++){                    
                            str1+=acc;
                        }
                        pair <int,string> ppp;
                        ppp.first=cnt;
                        ppp.second=str1;
                        str.push_back(ppp);
                    }else{                                                                
                        string ss=s.substr(ls,rs-ls);
                        cout<<ss<<endl;
                        cout<<cnt<<endl;
                        string str1;
                        for(int j=0;j<time;j++){                    
                            str1+=ss;
                        }

                        string str2;
                        if(!str.empty()){
                            str2=str.back().second;
                            int ttt=str.back().first;
                            str.pop_back();
                        }               
                            // str.push_back(str2+ss);
                        str1=str2+str1;
                        pair <int,string> ppp;
                        ppp.first=cnt;
                        ppp.second=str1;
                        str.push_back(ppp);
                        cout<<str1<<endl;                                            
                    }                   
                }
                flag=4;       
            }
        }
        // for(int i=0;i<num.size();i++){
        //     cout<<num[i]<<endl;
        // }
        // for(int i=0;i<str.size();i++){
        //     cout<<str[i]<<endl;
        // }
        ans=str.back().second;
        if(endnum+1 < s.length()){
            string endstr=s.substr(endnum+1,s.length()-endnum);
            // cout<<endstr<<endl;
            ans+=endstr;
        }        
        return ans;
    }
};

代码

class Solution {
public:
    string getString(vector <string> &v) {
        string ret;
        for (const auto &s: v) {
            ret += s;
        }
        return ret;
    }

    string decodeString(string s) {
        vector <string> stk;
        int ptr = 0;

        while (ptr < s.size()) {
            char cur = s[ptr];
            if (isdigit(cur)) {
                // 获取一个数字并进栈
                int i;
                for(i=ptr;i<s.size()&&isdigit(s[i]);i++){}
                string digits = s.substr(ptr,i);
                ptr=i;
                stk.push_back(digits);
            } else if (isalpha(cur) || cur == '[') {
                // 获取一个字母并进栈
                stk.push_back(string(1, s[ptr++])); 
            } else {
                ++ptr;
                vector <string> sub;
                while (stk.back() != "[") {
                    sub.push_back(stk.back());
                    stk.pop_back();
                }
                reverse(sub.begin(), sub.end());
                // 左括号出栈
                stk.pop_back();
                // 此时栈顶为当前 sub 对应的字符串应该出现的次数
                int repTime = stoi(stk.back()); 
                stk.pop_back();
                string t, o = getString(sub);
                // 构造字符串
                while (repTime--) t += o; 
                // 将构造好的字符串入栈
                stk.push_back(t);
            }
        }

        return getString(stk);
    }
};

代码（递归）

class Solution {
public:
    string src; 
    size_t ptr;

    int getDigits() {
        int ret = 0;
        while (ptr < src.size() && isdigit(src[ptr])) {
            ret = ret * 10 + src[ptr++] - '0';
        }
        return ret;
    }

    string getString() {
        if (ptr == src.size() || src[ptr] == ']') {
            // String -> EPS
            return "";
        }

        char cur = src[ptr]; int repTime = 1;
        string ret;

        if (isdigit(cur)) {
            // String -> Digits [ String ] String
            // 解析 Digits
            repTime = getDigits(); 
            // 过滤左括号
            ++ptr;
            // 解析 String
            string str = getString(); 
            // 过滤右括号
            ++ptr;
            // 构造字符串
            while (repTime--) ret += str; 
        } else if (isalpha(cur)) {
            // String -> Char String
            // 解析 Char
            ret = string(1, src[ptr++]);
        }

        return ret + getString();
    }

    string decodeString(string s) {
        src = s;
        ptr = 0;
        return getString();
    }
};

复杂度

O(N)

[Albert556]

class Solution { public: string getDigits(string &s, size_t &ptr) { string ret = ""; while (isdigit(s[ptr])) { ret.push_back(s[ptr++]); } return ret; }

string getString(vector <string> &v) {
    string ret;
    for (const auto &s: v) {
        ret += s;
    }
    return ret;
}

string decodeString(string s) {
    vector <string> stk;
    size_t ptr = 0;

    while (ptr < s.size()) {
        char cur = s[ptr];
        if (isdigit(cur)) {
            // 获取一个数字并进栈
            string digits = getDigits(s, ptr);
            stk.push_back(digits);
        } else if (isalpha(cur) || cur == '[') {
            // 获取一个字母并进栈
            stk.push_back(string(1, s[ptr++])); 
        } else {
            ++ptr;
            vector <string> sub;
            while (stk.back() != "[") {
                sub.push_back(stk.back());
                stk.pop_back();
            }
            reverse(sub.begin(), sub.end());
            // 左括号出栈
            stk.pop_back();
            // 此时栈顶为当前 sub 对应的字符串应该出现的次数
            int repTime = stoi(stk.back()); 
            stk.pop_back();
            string t, o = getString(sub);
            // 构造字符串
            while (repTime--) t += o; 
            // 将构造好的字符串入栈
            stk.push_back(t);
        }
    }

    return getString(stk);
}

};

[chenming-cao]

394. 字符串解码

官方题解

解题思路

用栈来解决。重复的部分满足格式k[encoded_string]，先将除]外的字符入栈，遇到]说明重复的部分出现，先出栈字母，再出栈[，最后出栈数字。根据数字将重复部分重新入栈。最后出栈所有字符获得字符串即为结果。

代码

class Solution {
    public String decodeString(String s) {
        Stack<Character> stack = new Stack<>();

        for (char c: s.toCharArray()) {
            if (c != ']') {
                stack.push(c); // push characters into stack if it is not ']'
            }
            else {
                StringBuilder sb = new StringBuilder();
                // get the repeated characters
                while (!stack.isEmpty() && Character.isLetter(stack.peek())) {
                    sb.insert(0, stack.pop());
                }

                String sub = sb.toString();
                // pop '[' from stack
                stack.pop();

                sb = new StringBuilder();
                // get the repeated times
                while (!stack.isEmpty() && Character.isDigit(stack.peek())) {
                    sb.insert(0, stack.pop());
                }

                int count = Integer.parseInt(sb.toString());
                // push the repeated characters back into stack
                while (count > 0) {
                    for (char element: sub.toCharArray()) {
                        stack.push(element);
                    }
                    count--;
                }
            }
        }

        StringBuilder res = new StringBuilder();
        while (!stack.isEmpty()) {
            res.insert(0, stack.pop());
        }

        return res.toString();
    }
}

复杂度分析

令字符串长度为n

• 时间复杂度：O(n)，需要遍历字符串
• 空间复杂度：O(n)，创建栈储存字符

[yetfan]

代码

class Solution:
    def decodeString(self, s: str) -> str:
        stack, res, multi = [], "", 0
        for c in s:
            if c == '[':
                stack.append([multi, res])
                res, multi = "", 0
            elif c == ']':
                cur_multi, last_res = stack.pop()
                res = last_res + cur_multi * res
            elif '0' <= c <= '9':
                multi = multi * 10 + int(c)            
            else:
                res += c
        return res

[GG925407590]

思路 将每个字符压入栈，如果遇到']'时弹出栈中内容到temp中，直到遇到'['才结束；如果遇到的是数字，则用add栈记录下来，与遇到'['出现时进行处理即可。

代码

class Solution {
public:
    string decodeString(string s) {
        vector<char> stack{};
        vector<char> temp{};
        vector<int> add{};
        int sum = 0;
        for (size_t i = 0; i < s.size(); i++) {
            if (std::isdigit(s[i])) {
                sum *= 10;
                int n = s[i] - '0';
                sum += n;
                continue;
            }else if (sum > 0) {
                add.push_back(sum);
                sum = 0;
            }

            if (s[i] == ']') {
                while(!stack.empty()) {
                    auto c = stack.back();
                    stack.pop_back();
                    if (c != '[') {
                        temp.push_back(c);
                    }else {
                        int times = add.back();
                        for (size_t i = 0; i < times; i++) {
                            stack.insert(stack.end(), temp.rbegin(), temp.rend());
                        }
                        add.pop_back();
                        temp.clear();
                        break;
                    }
                }
            }else {
                stack.push_back(s[i]);
            }
        }
        string result{};
        result.assign(stack.begin(), stack.end());
        return result;
    }
};

复杂度 时间复杂度：$O(n)$，需要遍历一遍字符 空间复杂度：$O(3n)$，主要来源于栈

[A-PolarBear]

class Solution {
public:
    string getDigits(string &s, size_t &ptr) {
        string ret = "";
        while (isdigit(s[ptr])) {
            ret.push_back(s[ptr++]);
        }
        return ret;
    }

    string getString(vector <string> &v) {
        string ret;
        for (const auto &s: v) {
            ret += s;
        }
        return ret;
    }

    string decodeString(string s) {
        vector <string> stk;
        size_t ptr = 0;

        while (ptr < s.size()) {
            char cur = s[ptr];
            if (isdigit(cur)) {
                // 获取一个数字并进栈
                string digits = getDigits(s, ptr);
                stk.push_back(digits);
            } else if (isalpha(cur) || cur == '[') {
                // 获取一个字母并进栈
                stk.push_back(string(1, s[ptr++])); 
            } else {
                ++ptr;
                vector <string> sub;
                while (stk.back() != "[") {
                    sub.push_back(stk.back());
                    stk.pop_back();
                }
                reverse(sub.begin(), sub.end());
                // 左括号出栈
                stk.pop_back();
                // 此时栈顶为当前 sub 对应的字符串应该出现的次数
                int repTime = stoi(stk.back()); 
                stk.pop_back();
                string t, o = getString(sub);
                // 构造字符串
                while (repTime--) t += o; 
                // 将构造好的字符串入栈
                stk.push_back(t);
            }
        }

        return getString(stk);
    }
};

[darwintk]

思路

使用递归的方法，每遇到一个“[”就递归一次，“]”return

代码

class Solution(object):
    def decodeString(self, s):
        def dfs(s, i):
            res, multi = "", 0
            while i < len(s):
                # 获取乘数
                if '0' <= s[i] <= '9':
                    multi = multi * 10 + int(s[i])
                # 左括号则递归获取字符串
                elif s[i] == '[':
                    i, tmp = dfs(s, i + 1)
                    res += multi * tmp
                    multi = 0
                # 右括号则返回需要拼接的字符串
                elif s[i] == ']':
                    return i, res
                # 字母则直接接到后面
                else:
                    res += s[i]
                i += 1
            return res
        return dfs(s,0)

复杂度

时间复杂度 O(n) 空间复杂度 O(n) n为字符串长度

[rzhao010]

Thoughts

Use Stack to push characters of s, stop when it hits ], and then gather the characters, read the multiplier, finally push all characters into the stack and pop out

Complexity

Time: O(N), N is the length of s Space: O(N) the use of stack

Code

class Solution {
    public String decodeString(String s) {
        Stack<Character> stack = new Stack<>();

        for (char c: s.toCharArray()) {
            if (c != ']') {
                stack.push(c);
            } else {
                StringBuilder sb = new StringBuilder();
                while (!stack.isEmpty() && Character.isLetter(stack.peek())) {
                    sb.insert(0, stack.pop());
                }
                String sub = sb.toString();
                stack.pop(); // remove [

                sb = new StringBuilder();
                while(!stack.isEmpty() && Character.isDigit(stack.peek())) {
                    sb.insert(0, stack.pop());
                }
                int count = Integer.valueOf(sb.toString());

                while (count > 0) {
                    for (char su: sub.toCharArray()) {
                        stack.push(su);
                    }
                    count--;
                }
            }
        }

        StringBuilder res = new StringBuilder();
        while (!stack.isEmpty()) {
            res.insert(0, stack.pop());
        }
        return res.toString();
    }
}

[neado]

思路

用列表模拟栈 先入栈，碰到 】 再出栈 先循环到[ 拼接字符 碰到 【，出栈 再拼接数字 循环字符串 数字值 遍 返回

代码

 class Solution(object):
    def decodeString(self, s):
        """
        :type s: str
        :rtype: str
        """
        # 定义列表
        stack=[]

        # 遍历字符串
        for c in s:
            # 出栈
            if c == ']':
                strT= ''
                count=''
                # 没碰到 [ 不停止循环
                while stack and stack[-1] !='[':
                    # 栈顶，即列表末尾元素弹出并返回值
                    strT =stack.pop() +strT 

                # 弹出 [
                stack.pop()
                # 碰到非数字再跳出循环
                while stack and stack[-1].isnumeric():
                    count =stack.pop() +count;
                stack.append(strT * int(count))
             # 入栈
            else:
                stack.append(c)
        return "".join(stack)
            }
        }
        return res.toString();
    }
}

复杂度分析

Time：O(N) Space:O(N)

[huiminren]

题目

LC394 字符串解码

思路一

括号匹配
入栈，遇到右括号出栈，记录str，左侧加value，直到遇到左括号
重复数字n次，入栈
所有数据出栈合并
------------
错误点，数字不仅是10以内的数

代码一

class Solution(object):
    def decodeString(self, s):
        """
        :type s: str
        :rtype: str
        """
        stack = []
        for i in range(len(s)):
            if s[i] == ']':
                tmp = ''
                while stack[-1] != '[':
                    tmp = stack[-1] + tmp
                    stack.pop()

                stack.pop() # 去掉 [
                # 获取数字
                repeat,e = 0,0
                while len(stack)>0 and stack[-1].isdigit():
                    repeat += int(stack[-1]) * (10**e)
                    e += 1
                    stack.pop() # 去掉数字
                stack.append(repeat*tmp)
            else:
                stack.append(s[i])

        ans = ''
        for v in stack:
            ans += v

        return ans

复杂度一

时间复杂度 O(S)
空间复杂度 O(S)

思路二

逆波兰式，字母一个栈，数字一个栈
巧妙点：上一个str和下一个要重复次数的数字，存成一个数组

代码二

class Solution(object):
    def decodeString(self, s):
        """
        :type s: str
        :rtype: str
        """
        num = 0
        string = ''
        stack = []
        for i in s:
            if i.isdigit():
                num = num*10 + int(i)                                
            elif i == '[':
                stack.append((string, num))
                string = ''
                num = 0
            elif i == ']':
                pre, k = stack.pop()
                string = pre + k * string
            elif i.isalpha():
                string += i
        return string

复杂度二

时间复杂度 O(S)
空间复杂度 O(S)

[H-steven]

• Stack

  class Solution:
  def decodeString(self, s: str) -> str:
      ans = []
      stack = []
      for i in range(len(s)):
          stack.append(s[i])
          if s[i] == ']':
              j = len(stack) - 1
              while j > 0:
                  if stack[j] == '[':
                      k = j - 1
                      while k >= 0 and ('0' <= stack[k] <= '9'):
                          k -= 1
                      temp = stack[j + 1:-1] * int("".join(stack[k + 1: j]))
                      stack = stack[: k + 1] + temp
                      break
                  j -= 1
      return "".join(stack)

[y4h2]

class Solution:
    def decodeString(self, s: str) -> str:
        if s.find('[') == -1:
            return s
        bracketStack = []
        digitStack = []
        n = len(s)

        leftBracket, rightBracket = -1, -1
        digitPos = -1
        digit = -1
        for i in range(n):
            if s[i].isdigit():
                if digitPos == -1:
                    digitPos = i

                digitStack.append(int(s[i]))

            if s[i] == '[':
                if digit == -1:
                    digit = self.getDigit(digitStack)
                bracketStack.append(i)
                if leftBracket == -1:
                    leftBracket = i
            if s[i] == ']':
                bracketStack.pop()
                if len(bracketStack) == 0:
                    rightBracket = i               
                    break

        a = s[:digitPos]
        b = digit * self.decodeString(s[leftBracket+1: rightBracket])
        c = self.decodeString(s[rightBracket+1:])

        return  a + b + c

    def getDigit(self, stack: List[int]) -> int:
        result = 0
        for num in stack:
            result = result * 10 + num

        return result

[MischaQI]

Complexity:

Time & Space: O(S)

Solution 1: Stack

Idea:

见到], 出栈字符串，出栈数字，重新入栈字符串

Code:

class Solution:
    def decodeString(self, s: str) -> str:
        stk = []
        for c in s: 
            if c == ']':
                repeatStr = ''
                repeatCount = ''
                while stk and stk[-1]!='[':
                    repeatStr = stk.pop() + repeatStr
                stk.pop()
                while stk and stk[-1].isdigit():
                    repeatCount = stk.pop() + repeatCount
                stk.append(repeatStr * int(repeatCount))
            else:
                stk.append(c)
        return "".join(stk)  

Solution 2: Iterative

Idea:

碰到左括号进⼊递归，碰到右括号就跳出递归返回

Code:

class Solution: 
    def decodeString(self, s: str) -> str:
        def dfs(start):
            repeatStr = repearCount = '' # 
            while start < len(s):
                if s[start].isdigit():
                    repearCount += s[start]
                elif s[start] == '[': # 进入递归条件
                    start, t_str = dfs(start+1)
                    print (start, t_str)
                    repeatStr = repeatStr + t_str*int(repearCount) # 之前递归的结果相加
                    repearCount = ''
                elif s[start] == ']': # 退出递归条件
                    return start, repeatStr
                else: # 最小子问题情况
                    repeatStr += s[start]
                start += 1
            return repeatStr
        return dfs(0)