Java 18ms solution


  • 0
    H
    public class Solution {
        public List<Integer> findSubstring(String s, String[] words) {
            int num=words.length;
            int leng=words[0].length();
            HashMap<String,Integer> map=new HashMap<String,Integer>();
            for(String w:words){
                if(!map.containsKey(w)){
                    map.put(w,1);
                }else{
                    map.put(w,map.get(w)+1);
                }
            }
            List<Integer> l=new ArrayList<>();
        
            for(int i=0;i<leng;i++){
                // count indicates how many "valid" words we have seen consecutively in the current search
    
                int count=0;
                HashMap<String,Integer> mapC=new HashMap<String,Integer>();
                for(int j=i; j+leng<=s.length();j+=leng){
                    String temp=s.substring(j,j+leng);
                    if(!map.containsKey(temp)){
    
                        count=0;
                        mapC.clear();
                    //keep going
                    }else if(!mapC.containsKey(temp)){
                        mapC.put(temp,1);
                        count++;
                    //keep going
                    }else if(mapC.get(temp)<map.get(temp)){
                        mapC.put(temp,mapC.get(temp)+1);
                        count++;
                    //we need to "invalidate" all words we have seen before the last occurrence of temp
                    }else{
                        int k=j-count*leng;
                        while(!s.substring(k,k+leng).equals(temp)){
                            String t=s.substring(k,k+leng);
                            mapC.put(t,mapC.get(t)-1);
                            count--;
                            k+=leng;
                        }
                     }
                     if(count==num){
                   
                         l.add(j-leng*num+leng);
                     }
                }
    
        }
        return l;
    }

Log in to reply
 

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