算法：字符串解码

发布日期: 2020-05-29

题目：字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例:

s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/decode-string

分析

方法一

首先讲一下我拿到这道题的思路：递归。每一歌中括号可以是一层，然后递归返回中括号中的字符串，和外层的数字进行循环重复后继续下一个中括号。例如：2[4[ab]]3[b]

先得到2，然后递归进入第一个中括号
得到4，递归进入
得到ab，遇到]返回上一层
ab进行4次重复，遇到]返回上一层
把得到的字符串进行2次重复。然后继续下一组。

思路应该是挺清晰的。但是这里有几个问题：在第五步的时候怎么确定下一组开始的位置？每一步递归，怎么确认开始的位置？我当时就卡在第一个问题，不知道如何解决。

对于第二个问题，很简单，重新写一个方法来递归，然后加入position参数即可。第一个问题有两个思路：

全局变量
在返回参数中加入

我比较喜欢第二种。因为全局变量就破坏了封装，我觉得不可取。但是返回参数，不是字符串吗，怎么附带位置信息？这里有个很好的解决方案：字符串数组。返回的字符串数组中一个保存得到的字符串，一个是数字字符串，再进行转换就可以得到位置信息了。思路到此应该就差不多了。另外的实现细节可以自己补充。

方法二

有递归，那么和递归一样思路的是什么？没错就是栈，那么我们可以使用一个辅助栈解决这个问题。思路和递归是差不多的：

遍历字符串数组并把字符放进栈。
当遍历到]时进行回溯，把中距离栈顶第一个[前的字符串拿出来
然后再遍历数字，遇到栈底或者]停止
然后进行循环运算后把字符串放进栈中
最后返回栈中的字符串

解答

方法一

fun decodeString(s: String): String{
    return getStrings(s,0)[0]
}
fun getStrings(s:String,i:Int):StringArray{
    val stringBuilder = StringBuilder()
    var num = 0
    var position = i
    while (position<s.length){
        if (s[position] in 'a'..'z' || s[position] in 'A'..'Z'){
            stringBuilder.append(s[position])
        }else if (s[position] in '0'..'9'){
            num = num*10 + s[position].toInt()-48
        }else if (s[position]=='['){
            val stringArray = getStrings(s,position+1)
            position = stringArray[1].toInt()
            while (num!=0){
                stringBuilder.append(stringArray[0])
                num--
            }
        }else if (s[position]==']'){
            val stringArray = StringArray()
            stringArray.add(stringBuilder.toString())
            stringArray.add(position.toString())
            return stringArray
        }
        position++
    }
    val stringArray = StringArray()
    stringArray.add(stringBuilder.toString())
    stringArray.add(position.toString())
    return stringArray
}

方法二

fun decodeString(s: String): String{
    if (s.isEmpty()) return ""
    val stack = Stack<Char>()
    for (c in s){
        if (c == ']'){
            val stringBuilder = StringBuilder()
            while (stack.peek()!='['){
                stringBuilder.append(stack.pop())
            }
            stack.pop()
            val string = stringBuilder.reverse().toString()

            var num = 0
            var i = 0
            while (stack.isNotEmpty() && stack.peek()>='0' && stack.peek()<='9'){
                val topNum = stack.pop().toInt()-48
                val p = 10.toDouble().pow(i)
                num += topNum*p.toInt()
                i++
            }

            for (j in 1..num){
                stack.addAll(string.toList())
            }
        }else stack.add(c)
    }
    val sb = StringBuilder()
    while (stack.isNotEmpty()){
        sb.append(stack.pop())
    }
    sb.reverse()
    return sb.toString()
}