Decode String

394. Decode String

Given an encoded string, return its decoded string.

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

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

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.

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.

 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.

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:

"abc3" => "abccc"

"abc3def" => "abcccdef"

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

"abc[de2f]2abc" => "abcdeefdeefabc"

"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

  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

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