0394. 字符串解码 Decode String

问题描述

这个问题也需要用栈, 因为有先入后入的操作. 但不同之处在于要使用两个栈, 分别存储数字和字符串.

另外, 在遍历字符串时, 要分别拼装数字和字符串.

以 3[a]2[bc] 为例:

代码实现

Rust

#![allow(unused)]
fn main() {
// Stack
pub fn decode_string1(s: String) -> String {
    assert!(!s.is_empty());

    // 用于存储 '[' 之前的数字, 可能是多位数.
    let mut num_stack: Vec<i32> = Vec::new();
    // 存储 '[' 之前的字符串.
    let mut str_stack: Vec<Vec<char>> = Vec::new();

    let chars: Vec<char> = s.chars().collect();
    // 存放当前的字符串.
    let mut parts: Vec<char> = Vec::new();
    // 存放当前的数字.
    let mut num: i32 = 0;

    for chr in chars {
        match chr {
            chr if chr.is_ascii_digit() => {
                // 处理数字
                let digit = chr.to_digit(10).unwrap() as i32;
                num = num * 10 + digit;
            }
            '[' => {
                // 将 '[' 之前的数字和字符串入栈.
                num_stack.push(num);
                str_stack.push(parts.clone());

                // 并重置它们.
                parts.clear();
                num = 0;
            }
            ']' => {
                // 收网, 从两个栈中分别取出整数和字符串, 进行一次拼装,
                // 然后将拼装结果入字符串栈.
                //
                // curr_num 是当前字符串重复次数.
                let curr_num = num_stack.pop().unwrap();
                // last_parts 是 '[' 之前的字符串, 相当于当前字符串的前缀.
                let last_parts = str_stack.pop().unwrap();
                // 合成的新的字符串.
                // parts = last_parts + curr_parts * curr_num.
                let curr_parts = parts;
                parts = last_parts;

                for _i in 0..curr_num {
                    parts.extend_from_slice(&curr_parts);
                }
            }
            letter => {
                // 拾取所有字符
                parts.push(letter);
            }
        }
    }

    // 组装最后的字符串
    parts.into_iter().collect()
}
}

C++

#include <cassert>

#include <stack>
#include <string>

std::string decode_string(std::string s) {
  // 数字栈, 用于存放遇到的数字.
  std::stack<int> num_stack;
  // 字符串栈, 用于存放中间的字符串.
  std::stack<std::string> str_stack;

  // 存放当前的数字
  int num = 0;
  // 存放当前的字符串
  std::string letters;

  for (char chr : s) {
    if (std::isdigit(chr)) {
      // 数字
      const int digit = static_cast<int>(chr - '0');
      num = num * 10 + digit;
    } else if (chr == '[') {
      // 将当前的数字和字符串入栈
      num_stack.push(num);
      num = 0;

      str_stack.push(letters);
      letters.clear();
    } else if (chr == ']') {
      // 遇到了右括号, 进行字符串的拼装.
      int last_num = num_stack.top();
      num_stack.pop();

      // new_letters = last_str + last_num * letters
      std::string last_str = str_stack.top();
      str_stack.pop();

      std::string new_letters = last_str;
      for (int i = 0; i < last_num; ++i) {
        new_letters += letters;
      }
      letters = new_letters;
    } else {
      // 其它字符
      letters += chr;
    }
  }

  return letters;
}