String Compression and Run-Length Encoding

Sanjeev SharmaSanjeev Sharma
2 min read

Advertisement

Problems

  1. Compress string: aabcccdddda2bc3d4
  2. In-place compression (LeetCode 443): modify char array in-place
  3. Decode: 3[a2[bc]]abcbcabcbc

In-Place String Compression — LeetCode 443

def compress(chars):
    write = read = 0
    while read < len(chars):
        curr = chars[read]
        count = 0
        while read < len(chars) and chars[read] == curr:
            read += 1; count += 1
        chars[write] = curr
        write += 1
        if count > 1:
            for c in str(count):
                chars[write] = c
                write += 1
    return write

Decode String — LeetCode 394

def decodeString(s):
    stack = []
    curr_str = ''
    curr_num = 0
    for c in s:
        if c.isdigit():
            curr_num = curr_num*10 + int(c)
        elif c == '[':
            stack.append((curr_str, curr_num))
            curr_str, curr_num = '', 0
        elif c == ']':
            prev_str, num = stack.pop()
            curr_str = prev_str + num*curr_str
        else:
            curr_str += c
    return curr_str

JavaScript

function decodeString(s){
    const stack=[]; let str='',num=0;
    for(const c of s){
        if(c>='0'&&c<='9')num=num*10++c;
        else if(c==='['){stack.push([str,num]);str='';num=0;}
        else if(c===']'){const[prev,n]=stack.pop();str=prev+str.repeat(n);}
        else str+=c;
    }
    return str;
}

Java

import java.util.*;
public String decodeString(String s){
    Deque<String>strStk=new ArrayDeque<>(); Deque<Integer>numStk=new ArrayDeque<>();
    StringBuilder cur=new StringBuilder(); int num=0;
    for(char c:s.toCharArray()){
        if(Character.isDigit(c))num=num*10+(c-'0');
        else if(c=='['){strStk.push(cur.toString());numStk.push(num);cur=new StringBuilder();num=0;}
        else if(c==']'){int n=numStk.pop();String prev=strStk.pop();cur=new StringBuilder(prev+cur.toString().repeat(n));}
        else cur.append(c);
    }
    return cur.toString();
}

C++

#include <stack>
#include <string>
using namespace std;
string decodeString(string s){
    stack<string>ss; stack<int>ns; string cur; int num=0;
    for(char c:s){
        if(isdigit(c))num=num*10+(c-'0');
        else if(c=='['){ss.push(cur);ns.push(num);cur="";num=0;}
        else if(c==']'){int n=ns.top();ns.pop();string prev=ss.top();ss.pop();string rep;for(int i=0;i<n;i++)rep+=cur;cur=prev+rep;}
        else cur+=c;
    }
    return cur;
}

C

/* C: explicit stack of (string, count) pairs */

Advertisement

Sanjeev Sharma

Written by

Sanjeev Sharma

Full Stack Engineer · E-mopro