3ms Simple Java Recursive Solution


  • 0

    The idea is to use DFS to find the solution. Each time we find a '[' we solve it recursively and when we encounter ']' the call is end.
    So to make sure that we're gonna encounter '[' and ']' both one time in each recursion, I have do the following thing:

    1. Create a global variable strIndex;
    2. Adjust the input, surround it with '1[' and ']'.
    public class Solution {
        private int strIndex;
        
        public String decodeString(String s) {
            // Adapt the input to my algorithm
            return dfs("1[" + s + "]").toString();
        }
        
        private StringBuilder dfs(String s) {
            StringBuilder cur = new StringBuilder();
    
            for (int k = 0; strIndex < s.length(); ++strIndex) {
                char c = s.charAt(strIndex);
                if (c >= '0' && c <= '9') { // Calculate the number K
                    k = k * 10 + c - '0';
                } else if (c == '[') { // Recursive step
                    ++strIndex;
                    StringBuilder sb = dfs(s);
    
                    for (; k > 0; k--) cur.append(sb);
                } else if (c == ']') { // Exit the loop and return the result.
                    break;
                } else {
                    cur.append(c);
                }
            }
            
            return cur;
        }
    }
    

Log in to reply
 

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