decode-string（挺麻烦的）

Java String作为参数传参是不会改变的，这个与常识的感觉不同。

public String decodeString(String s) {
        s = "";
        return s;
}

String s = "3[a2[c]]";
String ret = solution.decodeString(s);
System.out.printf("Get ret: %s
", s);

结果：
Get ret: 3[a2[c]]

下面是正题和解法：

https://leetcode.com/problems/decode-string/

// 唉，还是做的太慢了

package com.company;

import java.util.*;

class Solution {
    class Ret {
        String str;
        int pos;
    }
    String s;
    int slen;

    Ret parse(int index) {
        // 只能以数字或者字母开头
        Ret ret = new Ret();
        StringBuilder sb = new StringBuilder();

        while (index < slen && s.charAt(index) >= 'a' && s.charAt(index) <= 'z') {
            sb.append(s.charAt(index));
            index++;
        }
        String prefix = sb.toString();

        while (index < slen) {

            if (s.charAt(index) == ']') {
                break;
            }

            int multi = 0;
            while (index < slen && s.charAt(index) >= '0' && s.charAt(index) <= '9') {
                multi = multi * 10 + s.charAt(index) - '0';
                index++;
            }

            //System.out.println("start pos is " + index + " multi " + multi);

            if (s.charAt(index) == '[') {
                Ret tmpRet = parse(index+1);
                sb = new StringBuilder();
                for (int i = 0; i < multi; i++) {
                    sb.append(tmpRet.str);
                }
                index = tmpRet.pos + 1;
                //System.out.println("pos is " + index + " multi " + multi + " sb " + sb.toString());
            }
            else {
                sb = new StringBuilder();
                while (index < slen && s.charAt(index) >= 'a' && s.charAt(index) <= 'z') {
                    sb.append(s.charAt(index));
                    index++;
                }
            }

            prefix += sb.toString();
            //System.out.println("prefix is " + prefix);

        }

        //System.out.println("index" + index + " prefix" + prefix);
        ret.str = prefix;
        ret.pos = index;

        return ret;
    }

    public String decodeString(String s) {
        this.s = s;
        this.slen = s.length();
        Ret ret = parse(0);
        return ret.str;
    }
}

public class Main {

    public static void main(String[] args) {
        System.out.println("Hello!");
        Solution solution = new Solution();

        String s = "2[abc]3[cd]ef";
        String ret = solution.decodeString(s);
        System.out.printf("Get ret: %s
", ret);

        System.out.println();

    }
}


// 以下是原来的

public class Solution {
    private String s;
    private int newPos;
    
    public String decodeString(String ins) {
        s = '.' + ins + ']';
        newPos = 0;
        String outStr = impl(1, 0);
        return outStr.substring(1, outStr.length());
    }
    
    private String impl(int prefix, int startPos) {
        int base = 0;
        String baseStr = "";
        String outStr = "";
        
        for (int i=startPos; i<s.length(); i++) {
            char ch = s.charAt(i);
            
            if (ch == '[') {
                int tmpPos = i+1;
                baseStr += impl(base, tmpPos);
                i = newPos;
                base = 0;
            }
            else if (ch == ']') {
                for (int j=0; j<prefix; j++) {
                    outStr += baseStr;
                }
                // At begin, use i+1, is wrong,
                // because in each loop there's i++
                newPos = i;
                return outStr;
            }
            else if (!Character.isDigit(ch)){
                baseStr += ch;
            }
            else {
                base = base * 10 + ch - '0';
            }
        }
        
        return outStr;
    }
}