DFS solution for decode string problem, anyone help me to optimize?


  • 0
    public class Solution {
        public String decodeString(String s) {
            StringBuilder sb = new StringBuilder();
            dfs(s,sb);
            return sb.toString();
        }
        
        private void dfs(String s, StringBuilder sb){
            int i = 0;
            while(i < s.length()){
                while(i < s.length() && Character.isLetter(s.charAt(i))){
                    sb.append(s.charAt(i));
                    i++;
                }
                
                //get k
                int k = 0;
                while(i < s.length() && Character.isDigit(s.charAt(i))){
                    k = 10*k + (s.charAt(i) - '0');
                    i++;
                }
                
                //get string in the []
                if(i < s.length() && s.charAt(i) == '['){
                    int cntL = 0, start = i, end = 0;
                    while(i < s.length()){
                        if(s.charAt(i) == '[') cntL++;
                        if(s.charAt(i) == ']'){
                            cntL--;
                            if(cntL == 0){
                                end = i;
                                break;
                            }
                        }
                        i++;
                    }
                    String nextStr = s.substring(start+1, end);
                    for(int j = 0; j < k; j++){
                        dfs(nextStr, sb);
                    }
                }
                i++;
            }
        }
    }
    

Log in to reply
 

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