String Compression and Run-Length Encoding
Advertisement
Problems
- Compress string:
aabcccdddd→a2bc3d4 - In-place compression (LeetCode 443): modify char array in-place
- 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