575. Expression Expand

会了不难的好题,就是要稳稳地一步步来就好

复杂度O(n)地过一遍字符串,带着俩Stack存放上一层的数字和字符串,按照左右括号为号令地更新字符串和最终结果。

  1. 当遇到[ 时,除了数字要入栈再归零以外,也要把一个空字符串push到负责保存string的stack里。因为字符串的更新是要更新栈顶的,不压个空字符进去栈顶就是空的会null报错。
  2. 每当遇到 ] 时,如果stack不为空,还是要继续保持更新存string的栈顶。只有在string的栈为空时,才能直接添加到结果字符串里。
  3. 数字要一直n*10+c-’0’ 地计算,直到遇到 [ 再存入且归零,千万别按个位数字直接算

核心部分

for(int i=0; i<s.length(); i++){
 char c = s.charAt(i);
 if(Character.isDigit(c)){
 num= num*10 + (c-’0');
 continue;
 }
 if(Character.isLetter(c)){
 if(str.isEmpty()){
 res+=c;
 }
 else{ 
 str.push(str.pop()+c);
 }
 continue;
 }
 if(c==’[‘){
 count.push(num);
 num = 0;
 str.push(“”); 
 continue;
 }
 if(c==’]’){
 String t = “”;
 String temp = str.pop();
 int dup = count.pop();
 for(int k=0; k<dup; k++){
 t+=temp;
 }
 if(str.isEmpty()){
 res+=t;
 }else{ 
 str.push(str.pop()+t);
 }
 } 
 }

Like what you read? Give DeReK a round of applause.

From a quick cheer to a standing ovation, clap to show how much you enjoyed this story.