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();
}
Last updated
Was this helpful?