这几天看到一个大厂的面试题，感觉比较有意思，是学习递归的好题目，下面和大家分享一下这道题的解法。
题目说明：
压缩的字母规则是，连续相同的字母串压缩成：连续的个数 +[字母串]。如 aaa,压缩成:3[a]；amamam 压缩成 3[am]。
请实现解压缩字符串功能。实现程序语言不限制。完成时间两个小时，过程不能看手机，不能切屏。
自测样例，输入：3[k] 2[am] 预期输出：kkkamam
输入：2[k3[am]] 预期输出：kamamamkamamam
解题思路：
这个题目初看，解压缩的算法不难设计，只需要进行简单的递归就可以了，这里就不再赘述，而不用递归而且保证算法在o(n)时间内完成倒是有些难度。
这里需要用到栈的思想处理，倒序完成。
1.初始态中将输入字符串赋值给结果
2.找到最后一个[符号，取出其前面的数字以及与这个[最近的]符号，之间的所有字符，将这些字符串按照数字的个数展开，并用展开后的字符串对于数字[字符串]的原结构进行替换，保存到结果当中。
3处理完所有[即可完成解压。
代码如下：
import re def UnFoldString(repeat,strInput): if repeat<1: return None result="" for i in range(0,repeat): result=result+strInput return result def UnCompressString(strInput): pat = r'\d+' result=strInput numlist = re.findall(pat, strInput)#把所有数字通过re匹配出来，这个做法只适用于Python,后续可以优化 numIndex= len(numlist)-1#记录目前展开的位置 for j in range(0,len(result)):#遍历一次复杂度o(n) i= len(result)-1-j#关键在于使用栈的方式，从后找到最后一个[ if result[i]=='[': numlen=len(numlist[numIndex]) #print(numlen,i,numlist[numIndex],result[i-numlen:i]) if result[i-numlen:i]!=numlist[numIndex]:#如果最后一个[前面不是最后一个数字，肯定是有问题的 return None else: compressStr=result[i+1:].split(']')[0]#当前位置i对应的是[,那么从i+1到下一个]一定是要解压的字符，通过split方式最直观 comressStrLen=len(compressStr)+2 result=result[:i-numlen]+UnFoldString(int(numlist[numIndex]),compressStr)+result[i+comressStrLen:] numIndex=numIndex-1 return result strInput="3[k]2[am]" print(UnCompressString(strInput)) strInput="2[k3[am]]" print(UnCompressString(strInput)) strInput="12[k3[am]]" print(UnCompressString(strInput))
发散题目：
当然这题做到这肯定没结束，如果在面试中出现这道题目，我肯定会问对于压缩算法的实现策略，也就是把输入输出调转过来。
输入：kamamamkamamam 预期输出： 2[k3[am]]
这个想递归实现的方式都不简单。
可以先考虑下基本思路，因为这个结果需要嵌套，也就是左子串，右子串和中间你已经找到的最长子串都需要进行递归。
其中找最长的子串可以考虑贪心算法，直接按照字符串一半长度逐步尝试。
然后逐步向右移位。把左、右半边不在最长子串中的序列递归压缩。
具体代码及注释如下：
def FindMaxsubstring(strInput): #print(strInput) strlen=len(strInput) if strlen<2: return 0,strInput,strlen repeat=1 subStr="" if strlen==2: if strInput[0]==strInput[1]: return 2,strInput[0],strlen else: return 0,strInput,strlen for i in range(0,int(strlen/2)): greedyIndex=int(strlen/2)-i if greedyIndex<1: break repeatMax=int(strlen/greedyIndex) j=2 while strInput[:greedyIndex]==strInput[greedyIndex*(j-1):greedyIndex*j]: j=j+1 repeat=repeat+1 subStr=strInput[:greedyIndex] strlen=greedyIndex if repeat>1: return repeat,subStr,greedyIndex*repeat return 0, strInput, strlen def GenResult(strInput): repeat,lastRepeat=0,0 subStr,lastSubStr="","" lastLen=0 leftIndex=0 strLen=len(strInput) rightIndex=strLen if strLen<2: return strInput for i in range(0,strLen-1): lastRepeat,lastSubStr,lastRightIndex=FindMaxsubstring(strInput[i:]) if lastRepeat>1 and len(lastSubStr)>lastLen: #print(lastSubStr,str(i)) repeat=lastRepeat lastLen = len(lastSubStr) subStr=lastSubStr#递归生成子串 rightIndex=lastRightIndex leftIndex=i if repeat <2: return strInput if leftIndex<2 and (strLen-rightIndex)<2: return strInput[:leftIndex]+str(repeat)+"["+GenResult(subStr)+"]"+strInput[rightIndex+leftIndex:] else: return GenResult(strInput[:leftIndex]) + str(repeat) + "[" + GenResult(subStr) + "]" + GenResult(strInput[rightIndex+leftIndex:]) print(GenResult("kkkamam")) print(GenResult("kamamamkamamam"))
