压缩的字母规则是，连续相同的字母串压缩成：连续的个数 +[字母串]。如 aaa,压缩成:3[a]；amamam 压缩成 3[am]。
请实现解压缩字符串功能。实现程序语言不限制。完成时间两个小时，过程不能看手机，不能切屏。
自测样例，输入：3[k] 2[am] 预期输出：kkkamam
输入：2[k3[am]] 预期输出：kamamamkamamam
虽然我做了一下，结果调试没有问题，但是和最终结果还是有出入。大家可以自己做做。看是不是只有我觉得这个题目难，还是我太 low 了。
以下是我的实现，基于 python3.6：
import re
from string import digits
def untar_word(word,num):
'''
解压字符
:param word:
:param num:
:return:
'''
re_word = ''
for i in range(0,num):
re_word = re_word + word
return re_word
def get_number(word):
'''
提取数值list
:param word:
:return:
'''
return re.findall(r'\d+',word)
def del_digit(word):
'''
去除字符串中的数值
:param word:
:return:
'''
return word.translate(str.maketrans('', '', digits))
def deal_word(word):
'''
处理word
:param word:
:return:
'''
list_number = get_number(word)
new_words = del_digit(word)
deal_times = 0
a = -1 #记录处理的第几个压缩字符串
leve = 0
while True:
if deal_times == len(list_number):
break
else:
for i in range(0,len(new_words)):
if new_words[i] == '[':
a = a + 1
leve = leve + 1
mark = i
if new_words[i] == ']':
num = int(list_number[a])
word = new_words[(mark + 1):i]
new_words = new_words[0:mark] + untar_word(word,num) + new_words[i+1:]
deal_times = deal_times + 1
if leve > 1:
a = -1
break
return new_words
if __name__ == "__main__":
tar_word1 = '3[k]2[am]'
tar_word2 = '2[k3[am]]'
print(deal_word(tar_word1))
print(deal_word(tar_word2))
大佬们都开始拼算法了，写个其他解法，转成计算题
def unzip(data:str):
import re
pattern = r"(\D(?=[0-9]))|" \
r"([0-9](?=\[))"
def replace(matched):
value = ''
if matched.group(1):
value += matched.group(1) + "+"
if matched.group(2):
value += matched.group(2) + "*"
return value
data = re.sub(pattern, replace, data) # 转成数学计算
data = re.sub("[a-zA-Z]+", lambda x: f"'{x.group(0)}'", data) # 给字母加引号
return eval(data.replace("[", "(").replace("]", ")")) # 中括号替换
if __name__ == '__main__':
str_list = ["5[a]", "k3[k]2[am]", "2[[k10[am]]]", "x8[a1[pp]5[d]]"]
for s in str_list:
print(unzip(s))
改了下四楼大佬的算法，考虑了数字是多位的情况
def unzip(data):
stack = []
for e in data:
# 开始弹出
if e == ']':
tmp_str = ''
while stack:
item = stack.pop()
if item == '[':
continue
elif item.isdigit():
n = int(item)
# 处理所有的数字
loop = 1
while stack and stack[-1].isdigit():
n = int(stack.pop())*10**loop + n
loop += 1
tmp_str = n * tmp_str
break
# 如果是字母，则字符串相加
else:
tmp_str = item + tmp_str
stack.append(tmp_str)
else:
stack.append(e)
return "".join(stack)
print(unzip('101[k]'))
print(unzip('2[k10[am]]'))
print(unzip('2[am]'))
print(unzip('2[k]2[am]'))
kkkkkkkkkkkkkkkkkkkk
kamamamamamamamamamamkamamamamamamamamamam
amam
kkamam
这个可以转换成算术：
3[a] -> aaa 理解成 3*'a'
3[k] 2[am] -> kkkamam 理解成 3*'k' + 2*'am'
2[k3[am]] -> kamamamkamamam 理解成 2*('k'+3*'am')
解算术， 一般就是匹配， 入栈出栈。
如果把这个题目反过来， 看着难度会大增。
看代码风格 4 楼就赢了
综合楼上的一些思路，做了个 java 版。
public static String myUnzip(String testString){
StringBuilder strb = new StringBuilder();
int multi = 0;
//倍数栈，记录每个子串的倍数
Deque<Integer> stack_multi= new LinkedList<>();
//子串栈，记录子串
Deque<String> stack_strb= new LinkedList<>();
char[] c=testString.toCharArray();
for (int i = 0; i < c.length; i++) {
if(c[i] >= '0' && c[i] <= '9'){//如果遇到数字，就记录到倍数multi，如果遇到连续的数字，就进位组合成更高位数的数字
multi = multi * 10 + Integer.parseInt(c[i] + "");
}else if(c[i]=='['){//如果遇到左中括号，倍数进倍数栈，同时把multi置为0，用来记录下一个子串的倍数,当前子串清空
stack_multi.push(multi);
stack_strb.push(strb.toString());//记录[]内与倍数倍子串同级的串，例如acd3[b]中的acd
multi = 0;
strb = new StringBuilder();
}else if(c[i]==']'){//如果遇到右中括号，根据当前倍数拼接当前子串和同级的串，生成更外层[]中的子串
StringBuilder tmp = new StringBuilder();
int cur_multi = stack_multi.pop();//当前倍数
for(int j = 0; j < cur_multi; j++){
tmp.append(strb);
}
strb = new StringBuilder(stack_strb.pop() + tmp);
}else{//非数字和[]的情况，拼接
strb.append(c[i]);
}
}
return strb.toString();
}
递归应该也能做
@matt gong 按你的想法写，感觉写的好渣
def unzip(zip_data):
word = ''
for i,j in enumerate(zip_data):
if j == "[":
word = word + "*("
elif j == "]":
word = word + ")"
elif j.isalpha():
if not (zip_data[i-1].isalpha() or zip_data[i+1].isalpha()):
if zip_data[i+1].isdigit():
word = word + '"' + j + '"+'
else:
word = word + '"' + j + '"'
elif not zip_data[i-1].isalpha():
word = word + '"' + j
elif not zip_data[i+1].isalpha():
if zip_data[i+1].isdigit():
word = word + j + '"+'
else:
word = word + j + '"'
else:
word = word + j
else:
word = word + j
return eval(word)
我想知道反过来怎么解
是时候刷下 LeetCode 了
# 按照自己想法写的，比较low，轻喷
def unzip(zip_data):
y_index=zip_data.find(']')
if y_index==-1: #如果没有]跳出
return zip_data
else:
tmp_data=zip_data[:y_index]
z_index=len(tmp_data)-tmp_data[::-1].find('[')-1
num=""
for i in tmp_data[z_index-1::-1]:
if i.isdigit():
num=i+num
else:
break
z_data=tmp_data[:z_index-len(num)]
do_data=int(num)*tmp_data[z_index+1:y_index]
y_data=zip_data[y_index+1:]
ret_data=z_data+do_data+y_data
return unzip(ret_data)
测试这么卷的吗
class Solution(object):
def __init__(self, this_str: str):
self.this_str = this_str
def unzip(self):
return_str = ''
cal_str = ''
while len(self.this_str) > 0:
cur_word = self.this_str[0]
self.this_str = self.this_str[1:]
# 如果是字母
if 90 >= ord(cur_word) >= 65 or 122 >= ord(cur_word) >= 97:
return_str += cur_word
# 如果是[则进入递归，返回后防止同层级有多个压缩，需要重置倍率值
elif ord(cur_word) == 91:
z = self.unzip()
return_str += int(cal_str)*z
cal_str = ''
# 如果是]则返回中括号内的内容
elif ord(cur_word) == 93:
return return_str
# 如果是数字，则存入计算字符串中
elif 57 >= ord(cur_word) >= 48:
cal_str += cur_word
return return_str
目测用 “栈” 来搞是可以的;
c = []
e = ''
for i in list('3[am]2[bn]'):
if i == ']':
d = ''
for value in reversed(c):
if value == '[':
c.pop()
beishu = c.pop()
e = e + int(beishu) * d if d != '' else e+int(beishu) * e
break
else:
d = c.pop() + d
else:
c.append(i)
尝试写一下， 思路：编历字符串， 把其中数字、字母往栈里面丢， 不用管'['。 匹配到']', 取出栈中字符直到遇到数字，扩展后 (即数字 * 字母) 再放回栈。这样遍历完成后， 栈中放的就是所有扩展后的字母串， 取出来拼接好。
public class UnzipWords {
public static String unZipWords(String words){
/**
* 思路：编历字符串， 把其中数字、字母往栈里面丢， 不用管'['。 匹配到']', 取出栈中字符直到遇到数字，扩展后(即数字 * 字母)再放回栈。
* 这样遍历完成后， 栈中放的就是所有扩展后的字母串， 取出来拼接好。
*
*/
Deque<String> deque = new LinkedList<>();
for(char w : words.toCharArray()){
if(w==']'){
StringBuilder de_word = new StringBuilder();
while(!deque.isEmpty()){
String word = deque.pop();
if(word.length()==1 && Character.isDigit(word.charAt(0))){
int f = Integer.valueOf(word);
StringBuilder temp = new StringBuilder();
for(int i=1;i<=f;i++){
temp.append(de_word);
}
deque.push(temp.toString());
break;
}else{
de_word.insert(0,word);
}
}
}else if(w!='['){
deque.push(w+"");
}
}
StringBuilder sb = new StringBuilder();
while(!deque.isEmpty()){
sb.insert(0,deque.pop());
}
System.out.println(words + " -> " +sb.toString());
return sb.toString();
}
public static void main(String args[]){
unZipWords("3[k]4[x]");
unZipWords("2[k3[am]]");
unZipWords("x5[a4[c]5[d]m]");
unZipWords("3[K]");
}
}
示例：
3[k]4[x] -> kkkxxxx
2[k3[am]] -> kamamamkamamam
x5[a4[c]5[d]m] -> xaccccdddddmaccccdddddmaccccdddddmaccccdddddmaccccdddddm
3[K] -> KKK
https://leetcode-cn.com/problems/decode-string/ leetcode 原题
def parse(data: str):
data_list = []
for i in data:
if i != ']':
data_list.append(i)
else:
word, num = '', ''
while data_list[-1] != '[':
if 'A' <= data_list[-1] <= 'z':
word = data_list[-1] + word
data_list.pop()
else:
data_list.pop()
while data_list[-1] in '0123456789':
num = data_list[-1] + num
data_list.pop()
if not data_list:
break
data_list.append(int(num) * word)
return ''.join(i for i in data_list)
def flat(s):
def fla(mat):
cnt, s = mat.groups()
return int(cnt) * s
s = re.sub("(?:(\d+)\[(\w*)\])", fla, s)
if re.search("(?:(\d+)\[(\w*)\])", s):
return flat(s)
return s
备注：非算法，能简单解决问题的才是最有用的
群内大佬：atx uiautomator2 自动化群-->南京-DiN 解法
这题最简单的解法不就是栈吗，正则才是炫技吧
就 25 楼的答案，不上机测试有多少人能看明白结果对还是不对
def unzip(zip_data):
stack = []
for z in zip_data:
if z == "]": # 开始弹出
tmp_result = ""
while stack:
item = stack.pop()
if item == "[":
continue
if item.isdigit():
tmp_result = int(item) * tmp_result[::-1]
break
else:
tmp_result += item
stack.append(tmp_result)
else:
stack.append(z)
return "".join(stack)
测试样例
print(unzip("3[k]"))
print(unzip("3[k]4[x]"))
print(unzip("2[am]"))
print(unzip("2[k3[am]]"))
print(unzip("x5[a4[c]5[d]m]"))
kkk
kkkxxxx
amam
kmamamakmamama
xaccccdddddmaccccdddddmaccccdddddmaccccdddddmaccccdddddm
还不快一键三连？
挺有意思的题目，根据自己的思路也写了下，就是不知道执行怎么样
def deal_word(words):
word_list = re.findall(r'[a-z|A-Z]+', words)
for i in word_list:
words = words.replace(i, "'{}'".format(i))
special_word = re.findall(r"('\w+')\d+", words) # 处理字母后跟数字的情况
if special_word:
words = words.replace(special_word[0], '['+special_word[0]+']+')
words = words.replace('[', '*[').replace(']', ']+').strip('*').strip('+')
while ']+]' in words:
words = words.replace(']+]', ']]')
words = eval(words)
words = [''.join(w) for w in words]
return ''.join(words)
if __name__ == "__main__":
tar_word1 = '3[k]2[am]'
tar_word2 = '2[k3[am]]'
tar_word3 = '2[2[k3[am]]]'
print(deal_word(tar_word1))
print(deal_word(tar_word2))
print(deal_word(tar_word3))