Decompression

3[abb2[a]]2[b]ee > aaabbabbabbbbee

背景知識

array, defaultdict

理解問題

repeat次數[要repeat的字]

思路視覺化

3[abb2[a]]2[b]ee >  3[abb]2[b]ee, ret = [aa]
3[abb]2[b]ee > 2[b]ee, ret = [aa] [abbabbabb]
2[b]ee > ee, ret = [aa] [abbabbabb] [bb]
ee > , ret = [aa] [abbabbabb] [bb] [ee]
join, , ret = [aaabbabbabbbbee]

判斷數字次數加入dict, 遇到]處理  
{2:a, 3:abb,2:b} 
再 數字*次數
再補剩下ee

443. String Compression
394. Decode String

Java

// compression  
class Solution {
public int compress(char[] chars) {
    int ans = 0, i = 0;
    while(i < chars.length){
        char curr = chars[i];
        int count= 0;
        while(i < chars.length && chars[i] == curr){
            i++;
            count++;
        }
        chars[ans++] = curr;
        if(count != 1){
            for(char c: Integer.toString(count).toCharArray()){
                chars[ans++] = c;
            }
        }
    }
    return ans;
}

// decompression
public String decodeString(String s) {
        
        Stack<Character> stack = new Stack<>();
        
        for(char c : s.toCharArray()){
            if(c != ']') 
                stack.push(c); //push everything but ]
            else {

                // word
                StringBuilder sb = new StringBuilder();
                while(!stack.isEmpty() && Character.isLetter(stack.peek()))
                    sb.insert(0, stack.pop());
                
                String sub = sb.toString(); //this is the string contained in [ ]
                stack.pop(); //Discard '['
                
                // repeat times  
                sb.setLength(0); // clean
                while(!stack.isEmpty() && Character.isDigit(stack.peek()))
                    sb.insert(0, stack.pop());
                    
                int count = Integer.valueOf(sb.toString());
                
                //repeat word                
                while(count > 0){
                    for(char ch : sub.toCharArray())  
                        stack.push(ch);
                    count--;
                }
            }
        }
        
        // the rest
        StringBuilder ret = new StringBuilder();
        while(!stack.isEmpty())
            ret.insert(0, stack.pop());

        return ret.toString();
    }
}

Python

from collections import defaultdict

s = "3[abb2[a]]2[b]ee" # aaabbabbabbbbee
temp = defaultdict(list) # repeat:word {2:a, 3:abb,2:b} 
ret,repeat = [], 0

if len(s) == 0: print('')

for c in s:
    if c.isdigit():
        repeat = int(c)
    elif c.isalpha():
        temp[repeat].append(c)
    elif c == ']':
        if len(temp)!= 0:
            pair = temp.popitem()
        ret += ''.join(pair[1]*pair[0])
# the rest        
while len(temp)!=0:
    pair = temp.popitem()
    ret+=pair[1]
    
print(''.join(ret))

複雜度分析

TC: O(c+remain)
SC: O(n)

---

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)