← Strings

Decode String

Medium
Python
def decode_string(s):
    stack=[]; cs=''; cn=0
    for c in s:
        if c.isdigit(): cn=cn*10+int(c)
        elif c=='[': stack.append((cs,cn)); cs=''; cn=0
        elif c==']': ps,pn=stack.pop(); cs=ps+pn*cs
        else: cs+=c
    return cs
Java
public String decodeString(String s){
    Stack<Integer> ns=new Stack<>(); Stack<String> ss=new Stack<>();
    String cs=""; int cn=0;
    for(char c:s.toCharArray()){
        if(Character.isDigit(c)) cn=cn*10+(c-'0');
        else if(c=='['){ss.push(cs);ns.push(cn);cs="";cn=0;}
        else if(c==']'){int n=ns.pop();String p=ss.pop();cs=p+cs.repeat(n);}
        else cs+=c;
    } return cs;
}

Key Insight

Python tuple stack. n*string vs String.repeat().

Python → Java Differences

  • Python tuple stack vs Java two stacks
  • n*string vs String.repeat()
  • c-'0' vs int(c)
Python
def decode_string(s):
    stack=[]; cs=''; cn=0
    for c in s:
        if c.isdigit(): cn=cn*10+int(c)
        elif c=='[': stack.append((cs,cn)); cs=''; cn=0
        elif c==']': ps,pn=stack.pop(); cs=ps+pn*cs
        else: cs+=c
    return cs
Java
public String decodeString(String s){
    Stack<Integer> ns=new Stack<>(); Stack<String> ss=new Stack<>();
    String cs=""; int cn=0;
    for(char c:s.toCharArray()){
        if(Character.isDigit(c)) cn=cn*10+(c-'0');
        else if(c=='['){ss.push(cs);ns.push(cn);cs="";cn=0;}
        else if(c==']'){int n=ns.pop();String p=ss.pop();cs=p+cs.repeat(n);}
        else cs+=c;
    } return cs;
}

Algorithm Steps

1. [ save state
2. ] pop and repeat
← Previous All Strings Next →