--- 字符串解码 递归解法 通俗易懂 ---

给一个字符串，他按一定规律进行编码，对他进行解码，具体就不解释了，不过有个还需要知道，编码的字符串时有嵌套的情况的 比如 33[aa33[aa]] 这样

算法思想

a3[a]2[bc]

对这个字符串解码 那么会有这俩中情况 cur表示遍历到的数组下标

cur为字母，直接拼接到放回需要放回的字符串上

如果为数字，那么之后的字符就会设计到解码了

而者解码就涉及了三步

1 获取到数字 字符串解码的次数 x

2 获取到字符串

3 将字符串复制 x 次

之后将解码好的字符串拼接到最终结果中

如果不涉及到嵌套的解码话，那么以上这样就已经能够解决了额，但是是有这种情况的

所以解码方法中，也会涉及到相同的解码逻辑，这就可以使用递归了

所以 解码方法的具体逻辑应该时这样

// 获取到解码次数

// 获取到字符串 -> 判断是否有数字

有 递归 解码

没有 正常逻辑

// 复制字符串

// 放回解码好的字符串

大的方向就是这样，但是还涉及到几个细节问题

1. 最重要的 字符串的遍历问题， 因为在递归中，下标时不共享的，那么不知道当前已经递归到哪个下标，

方法一 可以将 返回值改为 单枪递归完的下标，把复制好的额字符串给作为全局变量，这样在方法中 把复制的字符串给评到全局变量中，但是又因为涉及到递归的原因，这个全局变量拼接时，会是反者的 具体来说是这样 2[aa1[bb]] -> bbaabbaa 因为他是从尾巴添加嘛，导致解码字符串顺序乱了，而且这样还会涉及到当前 ] 是谁的的问题，需要对放回的下标 ++ ，这样下标会跳跃起来，变得不可控和复杂，所以这样是不行的 （这是我第一次写的 没过 ）

方法二 既然会又字符串的顺序问题，那么就可以让他放回字符串，将放回的字符串又拼接到当前的需要复制的字符串后，就解决了，那下标的问题呢， 那就让下标改为全局的，正好这个下标也是不会回退一个一个的遍历整个字符串，很适合，且这样还可以少了解决 ] 和 下标跳跃的事

能解决

2 字符串的拼接

既然已经确定使用一个全局的下标遍历和放回解码好的字符串，那么其实者就很简单了，因为会将字符串放回，所以只需要一个作用域是方法的字符串就来拼接需要解码方法放回的字符串就行

其实只需要把第一个想出来，那么这题就很明朗了 尤其是放回解码好的字符串，之前想的是放回下标来解决方法之间的下标问题，这样下标会跳着走，特别麻烦和不可控

代码实现

// 全局的遍历下标 int cur = 0; public String decodeString(String s) { StringBuilder ans = new StringBuilder(); for (; cur < s.length(); cur++) { if (s.charAt(cur) >= '0' && s.charAt(cur) <= '9') { ans.append(dfs(s)); } else if (s.charAt(cur) >= 'a' && s.charAt(cur) <= 'z') { ans.append(s.charAt(cur)); } } return ans.toString(); } // dfs 表示处理一次3[ab] 的操作 cur 是第一次遇到了数字 返回的是]的下标 // cur开始这个位置可能 会有嵌套的 那么需要第字符串原地的修改 可以使用insert来对index位置插入字符串 // 这个储存最终要复制的字符串 StringBuilder dfs(String s) { // 当前的解码字符串 StringBuilder curCopy = new StringBuilder(); //获取到数字 int prev = cur; while (s.charAt(cur) >= '0' && s.charAt(cur) <= '9') cur++; String times = s.substring(prev, cur); // System.out.println("循环次数 " + times + " " + " p = " + prev + " c = " + cur); //获取到复制字符串 这里cur应该是[ prev = cur + 1; while (s.charAt(cur) != ']') { // 为数字说明嵌套了 if (s.charAt(cur) >= '0' && s.charAt(cur) <= '9') { curCopy.append(dfs(s)); // System.out.println("嵌套str " + curCopy); } else if (s.charAt(cur) >= 'a' && s.charAt(cur) <= 'z') { curCopy.append(s.charAt(cur)); } cur++; } // System.out.println("找到复制的字符串 " + curCopy + " " + " p = " + prev + " c = " + cur); // 循环添加 String tmp = curCopy.toString(); for (int i = 0; i < Integer.parseInt(times) - 1; i++) { curCopy.append(tmp); } // System.out.println(" 当前的解码字符串 " + curCopy + " " + " p = " + prev + " c = " + cur + " " + times); return curCopy; }