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
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.