Java recursive solution.


  • 1

    This solution is still using one pass to scan through String s because the helper function returns an index pointed to the next non-visited location in string s.

    public class Solution {
        int helper(char[] cc, int s, StringBuilder str){
            int i=s;
            for (; i< cc.length; i++) {
                if (cc[i] >='0' && cc[i] <='9') { // find repeat pattern
                    int count = (int) (cc[i++] -'0');
                    while (cc[i] != '[') {  // count repeating time
                        count = count*10 + (int) (cc[i++] -'0');
                    }
                    int start = ++i;
                    StringBuilder inner = new StringBuilder(); 
                    int end = helper( cc, start, inner ); // build the inner string of this repeat pattern
                    while ( count-- > 0 ) { 
                        str.append(inner); 
                    }
                    i=end; // move index to the next non-visited char
                } else if (cc[i]==']') { // ending of an inner pattern
                    return i; 
                } else { // not a repeat pattern
                    str.append(cc[i]);
                }
            }
            return i; // end of string s
        }
        
        public String decodeString(String s) {
            if ( s==null || s.length() == 0) return "";
            StringBuilder ret = new StringBuilder();
            helper(s.toCharArray(), 0, ret);
            return ret.toString();
        }
    }
    

  • 0

    @yubad2000 said in Java recursive solution.:

    This solution is still O(n)

    What is n?


  • 0

    @StefanPochmann
    Maybe I should have said using one pass to scan through String s, just like other iterative solutions, instead of O(n).
    :)


  • 0

    @yubad2000 Yeah, better change it to that. If n is the length of s, then O(n) is impossible (except maybe with a dirty hack).


Log in to reply
 

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