Java Simple Recursive Solution.


  • 0
    D
    public String decodeString(String s) {
        int lBracket = s.indexOf('[');
        if (lBracket == -1) return s;
        
        // Parse how many times to encode
        int firstDigit = 0;
        for (int i = lBracket - 1; i >= 0; i--)
        {
            if (s.charAt(i) < '0' || s.charAt(i) > '9') {
                firstDigit = i + 1;
                break;
            }
        }
        int times = Integer.parseInt(s.substring(firstDigit, lBracket));
        
        // Find the matching bracket, might not be efficient. We probably can precompute the matching brackets
        int rBracket = findMatchingBracket(s, lBracket);
    
        StringBuilder sb = new StringBuilder();
        
        // left part
        sb.append(s.substring(0, firstDigit));
        
        // Middle part
        String decodedSubString = decodeString(s.substring(lBracket + 1, rBracket));
        for (int j = 0; j < times; j++)
        {
            sb.append(decodedSubString);
        }
        // right part
        sb.append(decodeString(s.substring(rBracket + 1)));
        
        return sb.toString();
    }
    
    private int findMatchingBracket(String s, int l)
    {
        int cnt = 1;
        for (int i = l + 1; i < s.length(); i++)
        {
            if (s.charAt(i) == '[') cnt++;
            else if (s.charAt(i) == ']')
            {
                cnt--;
                if (cnt == 0) return i;
            }
        }
        return -1;
    }

Log in to reply
 

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