2018-11-14 17:56:12

问题描述：

问题求解：

方法一、递归求解

最直观的解法就是递归来求了，并且很显然的这个问题可以使用递归来进行求解。

public String decodeString(String s) {        StringBuffer sb = new StringBuffer();        int num = 0;        for (int i = 0; i < s.length(); i++) {            if (Character.isDigit(s.charAt(i))) {                num = 0;                while (i < s.length() && Character.isDigit(s.charAt(i))) {                    num = num * 10 + (s.charAt(i) - '0');                    i++;                }                i--;            }            else if (s.charAt(i) == '[') {                int count = 1;                int j = i;                while (count != 0) {                    j++;                    if (s.charAt(j) == '[') count++;                    if (s.charAt(j) == ']') count--;                }                String tmp = decodeString(s.substring(i + 1, j));                for (int k = 1; k < num; k++) sb.append(tmp);                i = j;            }            else sb.append(s.charAt(i));        }        return sb.toString();    }

方法二、使用Stack求解

使用Stack求解的时候，最核心的思路就是当遇到'['的时候将当前sb 和 num进行压栈操作，当遇到‘]’的时候将堆栈中sb 和 num取出并对当前的字符串进行num次重复并串联到sb后面。

public String decodeString(String s) {        StringBuffer sb = new StringBuffer();        Stack
     
       stack1 = new Stack<>();        Stack
      
        stack2 = new Stack<>();        int k = 0;        for (char c : s.toCharArray()) {            if (Character.isDigit(c)) k = k * 10 + c - '0';            else if (c == '[') {                stack1.push(sb);                stack2.push(k);                sb = new StringBuffer();                k = 0;            }            else if (c == ']') {                int count = stack2.pop();                String tmp = sb.toString();                sb = stack1.pop();                for (int i = 0; i < count; i++) sb.append(tmp);            }            else sb.append(c);        }        return sb.toString();    }