Java nonrecursive solution, without a stack


  • 0
    R

    Here is my nonrecursive solution.
    Basic idea is to decode the simple '[]' pair which only has characters in it, do this from begnning to end until there isn't any '[]' pair left.

    public String decodeString(String s) 
    {
            //still has '[]' pair
            while (s.indexOf('[') != -1)
            {
                int start = 0;
                // search from index start
                while (s.indexOf('[', start) != -1)
                {
                    int indexleft = s.indexOf('[', start), i = indexleft - 1, num = 0, base = 1;
                    int indexnext = s.indexOf('[', indexleft + 1), indexright = s.indexOf(']', indexleft);
                    // there is a '[]' pair in current '[]' pair
                    if (indexnext != -1 && indexnext < indexright)
                    {
                        start = indexnext;
                        continue;
                    }
                    // get the num before '['
                    while (i >= 0 && s.charAt(i) >= '0' && s.charAt(i) <= '9')
                    {
                        num += base * (s.charAt(i) - '0');
                        base *= 10; i--;
                    }
                    // decode it
                    StringBuilder sb = new StringBuilder();
                    sb.append(s.substring(0, i + 1));
                    while (num-- > 0)
                    {
                        sb.append(s.substring(indexleft + 1, indexright));
                    }
                    sb.append(s.substring(indexright + 1));
                    s = sb.toString();
                    break;
                }
            }
    
            return s;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.