Java Simple Recursive solution


  • 11
    H

    the run time is 3 ms. And the method is really straight-forward: every time when you meet a number, it must be followed by [...], we just need to recursively call our method to decode "...", then repeat the result "num" times.

    '''
    public class Solution {
    public String decodeString(String s) {

        if (s.length() == 0) return "";
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i ++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                int digit_begin = i;
                while (s.charAt(i) != '[') i++;
                int num = Integer.valueOf(s.substring(digit_begin, i));
                int count = 1;
                int str_begin = i+1;
                i ++;
                while (count != 0) {
                    if (s.charAt(i) == '[') count ++;
                    else if (s.charAt(i) == ']') count --;
                    i ++;
                }
                i--;
                String str = decodeString(s.substring(str_begin, i));
                for (int j = 0; j < num; j ++) {
                    sb.append(str);
                }
            } else {
                sb.append(c);
            }
        }
        return sb.toString();
    }
    

    }
    '''


  • 2
    L

    Nice solution! Just a little modification based on yours:

        StringBuilder cur = new StringBuilder();
        int num = 0;
        for (int i = 0; i < s.length(); i++) {
            if (Character.isDigit(s.charAt(i))) {
                num = num * 10 + (s.charAt(i) - '0');
            } else if (s.charAt(i) == '[') {
                //find the matching ]
                int begin = i;
                i++;
                int count = 1; 
                while (count != 0) {
                    if (s.charAt(i) == '[') {
                        count++;
                    } else if (s.charAt(i) == ']') {
                        count--;
                    }
                    i++;
                }
                i--;
                
                String substr = decodeString(s.substring(begin + 1, i));
                for (int k = 0; k < num; k++) {
                    cur.append(substr);
                }
                num = 0;
            } else { 
                cur.append(s.charAt(i));
            }
        }
        return cur.toString();

  • 0
    M

    What is the time complexity?


  • 0

    Thanks for sharing!
    The code for finding the matching ']' could be optimized as follow to avoid several i++, i--.
    Plus wondering if the time complexity is O(n)? For every time of the recursion we would iterate every character of the string. That would be n+(n-k)+(n-k-k)..... (number and brackets are roughly constant length), so still linear time?
    And the space complexity is O(number of bracket pairs), am I correct?

               else if(s.charAt(i)=='['){
                int begin=i;
                int count=1;
                while(count>0){
                  i++;
                  if(s.charAt(i)=='[')    count++;
                  if(s.charAt(i)==']')    count--;
                }

  • 0
    D
    This post is deleted!

  • 1
    Z

    Nice solution, a bit shorter one:

    public class Solution {
        int ptr=0;
        public String decodeString(String s) {
            return helper(s,1);
        }
        public String helper(String s, int dup){
            String s_temp="",res="";
            while(ptr<s.length()&&s.charAt(ptr)!=']'){
                if(Character.isDigit(s.charAt(ptr))){
                    int num=0;
                    while(Character.isDigit(s.charAt(ptr))) num=num*10+s.charAt(ptr++)-'0';
                    ptr++;
                    s_temp+=helper(s,num);
                }
                else s_temp+=s.charAt(ptr++);
            }
            for(int i=0;i<dup;i++) res+=s_temp;
            ptr++;
            return res;
        }
    }
    

Log in to reply
 

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