Time Limit Exceeds solution, needs some help!


  • 0
    T

    The main idea of mine is that go through every string, to check wether we can use this current stick to deduct chars to target string. I use a while loop until we are not able to update the count of chars of target string, then we can go to the next index to repeat the above process. However, this solution is TLE, any idea how to improve it?

    class Solution {
        public int minStickers(String[] stickers, String target) {
             if(target==null || stickers==null){
                 return -1;
             }   
             char[] array = target.toCharArray();
             Map<Character,Integer> map = new HashMap<>();
             for(char c:array){
                map.put(c,map.getOrDefault(c,0)+1);   
             }
            
            char[][] dicts = new char[stickers.length][26];
            for(int i=0;i<stickers.length;i++){
                String ele=stickers[i];
                char[] arrayEle = ele.toCharArray();
                for(char c:arrayEle){
                    dicts[i][c-'a']++;
                }
            }
            
            return dfs(dicts,map,0);
        }
        
        public int dfs(char[][] dicts,Map<Character,Integer> map,int index){
            boolean finished = true;
            for(Character key:map.keySet()){
                if(map.get(key)>0){
                    //System.out.println("key :"+key+", count: "+map.get(key));
                    finished = false;
                    break;
                }
            }
            
            if(finished){
                return 0;
            }
            //System.out.println("now we are working on index:"+index);
            if(index>=dicts.length){
                return -1;
            }
            
            int min = Integer.MAX_VALUE;
            int count = dfs(dicts,map,index+1);
            if(count!=-1){
                min = count;
            }
            
            Map<Character,Integer> copyMap = new HashMap<>(map);
            
            boolean endLoop = false;
            int cnt = 0;
            while(endLoop == false){
               cnt++;
               endLoop = true;
               Set<Character> set = map.keySet();
               for(Character key:set){
                   if(dicts[index][key-'a']>0&&map.get(key)>0){
                      endLoop = false;
                      map.put(key,map.get(key)-dicts[index][key-'a']);
                   }
               }
               if(endLoop==false){
                   count = dfs(dicts,map,index+1);
                   //System.out.println("index: "+index+",cnt: "+cnt+", count: "+count+",map size: "+map.size());
                   if(count!=-1){
                       min = Math.min(min,count+cnt);
                   }
               }else{
                   break;
               }
              
            }
            
            //map = copyMap;
            for(char c:copyMap.keySet()){
                map.put(c,copyMap.get(c));
            }
            return min == Integer.MAX_VALUE?-1:min;
        }
    }
    

Log in to reply
 

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