# Decode String

## 394. Decode String

Given an encoded string, return its decoded string.

```python
Input: s = "3[a]2[bc]"
Output: "aaabcbc"
```

```python
def decodeString(self, s: str) -> str:
    stack = []
    line = ''
    num = 0
    i = 0
    
    while i < len(s):
        c = s[i]
        if c.isdigit():
            num = int(c)
            while i+1 < len(s) and s[i+1].isdigit():
                num = 10*num + int(s[i+1])
                i += 1
        elif c == '[':
            stack.append(line)
            stack.append(num)
            line = ''
            num = 0
        elif c == ']':
            pre_num = stack.pop()
            pre_line = stack.pop()
            pre_line += line * pre_num
            line = pre_line
        else:
            line += c
        i += 1
    return line
```

* Recursive: 放進recursion的string必須是完整\[]的內容,並更新index&#x20;

```java
public String decodeString(String s) {
    String str = "";
    int num = 0;

    for(int i=0; i<s.length(); i++){
        char c = s.charAt(i);
        if(Character.isDigit(c)) num = num*10 + c -'0';
        else if( c == '[') {
            int count = 1;
            int iter = i+1;
            while(count != 0){
                if(s.charAt(iter) == '[') count++;
                if(s.charAt(iter) == ']') count--;
                iter++;
            }
            iter--;
            String concate = decodeString(s.substring(i+1, iter));
            for(int j=0; j<num; j++){
                str += concate;
            }
            num = 0;
            i = iter;
        }else str += c;
    }
    return str;
}
```

## 443. Decode Compression

Given an array of characters, compress it [**in-place**](https://en.wikipedia.org/wiki/In-place_algorithm).

```java
Input:
["a","b","b","b","b","b","b","b","b","b","b","b","b"]

Output:
Return 4, and the first 4 characters of the input array should be: ["a","b","1","2"].

Explanation:
Since the character "a" does not repeat, it is not compressed. "bbbbbbbbbbbb" is replaced by "b12".
Notice each digit has it's own entry in the array.
```

```python
 def compress(self, chars: List[str]) -> int:
    n = len(chars)
    
    read, write = 0, 0        
    while read<n:
        c = chars[read]
        chars[write] = c
        write += 1
        count = 1
        while read+1 < n and chars[read+1] == c:
            read+=1
            count+=1
        read+=1
        
        if count > 1:
            for c2 in str(count):
                chars[write] = c2
                write +=1
    
    return write
```

## Valid Express (Bloomberg)

Given a string of balanced expression, find if it contains a redundant parenthesis or not. A set of parenthesis are redundant if same sub-expression is surrounded by unnecessary or multiple brackets.

```python
def validExpress(s):
  count = 0
  innest = False
  stack = []
  for c in s:
    if c in '+-*/': continue
    elif c == '(':
      stack.append(count)
      innest = True
      count = 0
    elif c == ')':
      if (innest and count <= 1) or (not innest and count == 0):
        return False
      count = stack.pop()
      innest = False
    else:
      count += 1
  return True

print(validExpress('((a+b))'))
print(validExpress('(a+(b)/c)'))
print(validExpress('(a*(c-d))'))
print(validExpress('(a+b*(c-d))'))

```

## Compress String (Quantcast)

Write a method that can take a "compressed" string and decompress it.

Example:&#x20;

"abc3" => "abccc"&#x20;

"abc3def" => "abcccdef"&#x20;

"abc\[def]2abc" => "abcdefdefabc"

&#x20;"abc\[de2f]2abc" => "abcdeefdeefabc"&#x20;

"abc\[def\[ghi]2def]2abc" => "abcdefghighidefdefghighidefabc"

* Assumptions:
*
  * Every closing bracket is followed by a number
*
  * Each non numeric character is either a-z, \[, or ]
* mark有無需要concate的string
* 碰到'\['要找到對應']'的index
*   碰到num兩種判斷: concate string or Char

    **Recursive**

    ```java
    static String compress2(String s) {
      String preString = "";
      String bracketString = "";
      boolean hasBracket = false;
      for(int i=0; i<s.length(); i++){
          char c = s.charAt(i);
          if(c >= 'a' && c<= 'z'){
              preString += c;
          }else if(c == '['){
              hasBracket = true;
              int iter = i+1;
              int count = 1;
              while(count != 0){
                  if(s.charAt(iter) == '[') count++;
                  else if(s.charAt(iter) == ']') count--;
                  iter++;
              }
              iter--;
              bracketString = compress2(s.substring(i+1, iter));
              i = iter;
          }else if(Character.isDigit(c)){
              int num = c - '0';
              while( i+1<s.length() && Character.isDigit(s.charAt(i+1))){
                  num = num*10 + s.charAt(i+1)-'0';
                  i++;
              }
              if(hasBracket){
                  for(int j=0; j<num; j++) {
                      preString += bracketString;
                  }
                  bracketString = "";
                  hasBracket = false;
              }else{
                  char copy = preString.charAt(preString.length()-1);
                  for(int j=0; j<num-1; j++){
                      preString += Character.toString(copy);
                  }
              }
          }
      }
      return preString;
    }
    ```

#### Iterative(較難)

* char & \[string] 都視為一個element
* 碰到char 放進stack
* 碰到'\[', poll stack until '\[', 組成string再放進stack, push '\['
* 碰到']', poll stack until '\[', 組成string再放進stack, poll '\['
* 數字就重複 poll的 string
* 最後reverse string

```java
static String compress1(String s) {
    Stack<String> stack = new Stack<>();

    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c >= 'a' && c <= 'z') {
            stack.push(Character.toString(c));
        } else if (c == '[') {
            StringBuilder sb = new StringBuilder();
            while (!stack.isEmpty() && !stack.peek().equals("[")) {
                sb.append(stack.pop());
            }
            stack.push(sb.toString());
            stack.push("[");
        } else if (Character.isDigit(c)) {
            int num = c - '0';
            while (i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))) {
                num = num * 10 + s.charAt(i + 1) - '0';
                i++;
            }
            StringBuilder sb = new StringBuilder();

            String concate = stack.pop();
            for (int j = 0; j < num; j++) {
                sb.append(concate);
            }
            stack.push(sb.toString());
        } else if (c == ']') {
            StringBuilder sb = new StringBuilder();
            while (!stack.peek().equals("[")) {
                sb.append(stack.pop());
            }
            stack.pop();
            stack.push(sb.toString());
            // cur = "";
        }
    }
    StringBuilder sb = new StringBuilder();
    while (!stack.isEmpty()) {
        sb.append(stack.pop());
    }
    return sb.reverse().toString();
}
```
