Straightforward Java solution, no data structure needed


  • 0
    J
    public String decodeString(String s) {
            int firstIndexOfClose;
            while ((firstIndexOfClose = s.indexOf("]")) >= 0) {
                int lastIndexOfOpening = s.substring(0, firstIndexOfClose).lastIndexOf("[");
                int numPos = lastIndexOfOpening - 1;
                while (numPos >= 0 && s.charAt(numPos) <= '9' && s.charAt(numPos) >= '0') {
                    numPos --;
                }
                int times = Integer.valueOf(s.substring(numPos + 1, lastIndexOfOpening));
                String substitutee = "";
                String inner = s.substring(lastIndexOfOpening + 1, firstIndexOfClose);
                for (int i=0; i<times; i++) {
                    substitutee += inner;
                }
                s = s.substring(0, numPos + 1) + substitutee + s.substring(firstIndexOfClose + 1);
            }
            return s;
        }
    

    Always find the first "]" character, which represents the end of either the innermost expression of a nested expression or a non-nested expression. Substitute it with the desired string, then recursively call this method on the new string.


  • 0
    5

    A nice solution but it is not a recursive solution as claimed.


  • 0
    J

    Well yeah, I'll change the title.


Log in to reply
 

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