Very Clear DFS solution with explain


  • 0
    T

    The idea is to go through the String, whenever we encounter a digit, we need to repeat the string inside the parenthesis after the digit, and that's when DFS comes here. Each time we encounter a ']', we return some encoded String and keeping scan the rest of the String. Here we need the end index of the ']' because we don't have to scan the char before this index. And that's why we need to store both string and ending index.

    class ReturnType {
        String val;
        int end;
        public ReturnType (String val, int end) {
            this.val = val;
            this.end = end;
        }
    }
    
    public class Solution {
        public String decodeString(String s) {
           //I add a ']' at the end of the String as a dummy parenthesis meaning we repeat the whole string one time
            s = s + ']';
            return help(s, 1, 0).val;
        }
        
        private ReturnType help(String s, int repeat, int i) {
            StringBuilder sb = new StringBuilder();
            
            for (int j = i; j < s.length(); j++) {
                if (Character.isDigit(s.charAt(j))) {
                    int num = 0;
                    while (Character.isDigit(s.charAt(j))) {
                        num = 10 * num + (s.charAt(j++) - '0');
                    }
                    ReturnType rt = help(s, num, j + 1);
                    sb.append(rt.val);
                 //We have to skip the chars already been encoded during the previous DFS
                    j = rt.end;
                } else if (s.charAt(j) == ']') {
                    String str = sb.toString();
                    for (int k = 0; k < repeat - 1; k++) {
                        sb.append(str);
                    }
                    return new ReturnType(sb.toString(), j);
                } else if (s.charAt(j) != '[') {
                    sb.append(s.charAt(j));
                } 
            }
            //Since I have already add a ']' at the end of the String, the result will return at the last index of the String inside the for loop 
            return null;
        }
    }
    

  • 0
    H

    very nice & clear explanation, thx


Log in to reply
 

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