Java Time Limit Exceeded


  • 0
    S

    Anyone spare a second to help me take a look at my code? Seems my solution gets Time Limit Exceeded and I am having a difficult time optimizing. Any ideas? :)

    class Solution {
        public String crackSafe(int n, int k) {
            StringBuilder sb = new StringBuilder();
            int len = (int)Math.pow(k, n) + (n-1);
            
            HashSet<String> set = new HashSet<>();
            generate(set, "", n, k);
            
            for(int i = 0; i < k; i++){
                for(int j = 0; j < n; j++){
                    sb.append(String.valueOf(i));
                    len--;
                    if(sb.length() >= n){
                        set.remove(new String(sb.substring(sb.length() - n)));   
                    }
                }
            }
            
            // System.out.println(len);
            helper(len, sb, set, n, k);
            return sb.toString();
        }
        
        
        public boolean helper(int len, StringBuilder sb, HashSet<String> set, int n, int k){
            if(len == 0){
                return true;
            }
            
            String curr = new String(sb.substring(sb.length() - n + 1));
            
            for(String s : set){
                if(s.startsWith(curr)){
                    String c = s.substring(s.indexOf(curr) + curr.length());
                    int l = sb.length();
                    sb.append(c);
                    // removes used string
                    HashSet<String> clone = (HashSet<String>)set.clone();
                    clone.remove(s);
                    if(helper(len - 1, sb, clone, n, k)){
                        return true;
                    }
                    sb.setLength(l);
                }
            }
            return false;
        }
        
        public void generate(HashSet<String> set, String curr, int n, int k){
            if(curr.length() == n){
                set.add(curr);
                return;
            }
            
            for(int i = 0; i < k; i++){
                generate(set, curr + String.valueOf(i), n, k);
            }
        }
    }
    

Log in to reply
 

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