Java solution


  • 0
    S

    High level explanation

    go thorugh string, when i see a digit keep going until i see [. 
        store this number repeatCount
        find the matching ]
        extract the encodedString
    
        sb.append(repeatCount * decodeString(encodedString))
        jump currChar to the char after ]
     if i dont see a digit, then it must be a char so add to sb
    
    class Solution {  
        public String decodeString(String s) {
            StringBuilder sb = new StringBuilder(); // 
            int i = 0; //0
            
            while (i < s.length()) {
                char currChar = s.charAt(i); // 3
                
                if (Character.isDigit(currChar)) {
                    int repeatCount = getRepeatCount(s, i); //3
                    int patternStartIndex = getPatternStartIndex(s, i); //2
                    int patternEndIndex = getPatternEndIndex(s, i); //
                    String pattern = s.substring(patternStartIndex, patternEndIndex+1); //
                    while (repeatCount != 0) {
                        sb.append(decodeString(pattern));
                        repeatCount--;
                    }
                    i = patternEndIndex + 1; //+1 because we want to skip the closing bracket ] after patternIndexEnd
                } else {
                    //if it's not a digit, then just a regular character so add it.
                    sb.append(currChar);
                }            
                i++;
            }
            
            return sb.toString();
        }
        
        //returns index of last digit before [
        private int getDigitIndexEnd (String s, int i) {
            int digitIndexStart = i; //0
            int digitIndexEnd = i; //0
            
            while (i < s.length() && Character.isDigit(s.charAt(i))) {
                digitIndexEnd = i;
                i++;
            }
                   
            return digitIndexEnd;
        }
        
        //s = encoded string, i = index of first digit
        private int getRepeatCount(String s, int i) {
            int digitIndexEnd = getDigitIndexEnd(s, i); //0
            return Integer.valueOf(s.substring(i, digitIndexEnd+1));
        }
        
        //s = encoded string, i = index of first digit before pattern, return index of first char in pattern
        private int getPatternStartIndex(String s, int i) {
            int digitIndexEnd = getDigitIndexEnd(s, i); //
            return digitIndexEnd + 2; //+2 because i want to skip the opening [
            
        }
                   
        
        //s = encoded string, i = index of first digit before pattern, returns index of the last char in pattern
        private int getPatternEndIndex(String s, int i) {
            
            //should never return -1, if i do, some grave error. please break;
            //go through the string to find the closing ].
            //if i see a [, then i put it on a stack.
            //if i see a ], then...
            /*
                is stack empty?
                    yes
                        hen i know i found the closing ]
                    no
                        pop the stack an keep going
            if i see a charr, keep going
            */
            
            i = getPatternStartIndex(s, i); //4
            int result = -1; //3
            Stack<Character> stack = new Stack<Character>();
            stack.push('[');
            
            while (!stack.isEmpty()) {
                result = i;
                
                char currChar = s.charAt(i);
                
                if (currChar == '[') {
                    stack.push(currChar);
                }
            
                if (currChar == ']') {
                    stack.pop();
                }
            
                i++;
            }
            
            
            return result-1; //3
        }
    }
    

Log in to reply
 

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