3ms Java recursive solution with detailed comments


  • 0
    R
    public class Solution {
        public String decodeString(String s) {
            StringBuilder stringBuilder = new StringBuilder();
            // Go through each character in the String
            for (int i = 0; i < s.length(); i++) {
                // If current character is an alphabetical character, we just need to add it to the stringBuilder
                char curr = s.charAt(i);
                if (curr >= 'a' && curr <= 'z') {
                    stringBuilder.append(curr);
                    continue;
                }
                // If it is not an alphabetical value, that means it is a digit and we need to parse for the number (until we find the starting bracket [)
                int bracketStart = i + 1;
                while (s.charAt(bracketStart) != '[')
                    bracketStart++;
                int multValue = Integer.parseInt(s.substring(i, bracketStart));
                // We now need to find the end of the bracket corresponding to the our starting bracket
                int numNested = 0;
                for (int j = bracketStart + 1; j < s.length(); j++) {
                    if (s.charAt(j) == '[') {
                        numNested++;
                        continue;
                    } else if (s.charAt(j) == ']') {
                        if (numNested-- != 0) continue;
                        // We have now found the end of the corresponding bracket. We can will recurse here and update the value of i
                        String recursiveString = decodeString(s.substring(bracketStart + 1, j));
                        for (int k = 0; k < multValue; k++) stringBuilder.append(recursiveString);
                        i = j;
                        break;
                    }
                }
            }
            return stringBuilder.toString();
        }
    }
    

Log in to reply
 

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