> For the complete documentation index, see [llms.txt](https://netjimmy.gitbook.io/code-interview-note/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://netjimmy.gitbook.io/code-interview-note/2.1-string/decode-string.md).

# 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();
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://netjimmy.gitbook.io/code-interview-note/2.1-string/decode-string.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.