Java 40lines O(n) solution beats 93% (let me know if you have trouble understand)


  • 0
    Y
    class Solution {
        public List<Integer> findSubstring(String s, String[] words) {
            int n=s.length(),w1=words.length,w2=words[0].length(),w3=w2*w1;
            Map<String,Integer> hmap=new HashMap<>();
            List<Integer> cs=new LinkedList<>();
            int count=1;
            for(int i=0;i<w1;i++){
                if(hmap.containsKey(words[i])){
                    int index=hmap.get(words[i])-1;
                    cs.set(index,cs.get(index)+1);
                }
                else{
                    hmap.put(words[i],count++);
                    cs.add(1);
                }
            }
            int[] benchMark=new int[cs.size()];
            for(int i=0;i<cs.size();i++) benchMark[i]=cs.get(i);
            
            int[] dp=new int[n];
            for(int i=0;i<=n-w2;i++){
                String subs=s.substring(i,i+w2);
                if(hmap.containsKey(subs)) dp[i]=hmap.get(subs);
            }
            
            List<Integer> result=new LinkedList<>();
            for(int i=0;i<w2;i++){
                int[] counts=new int[cs.size()];
                count=0;
                for(int j=i;j<n;j+=w2){
                    if(dp[j]>0) if(++counts[dp[j]-1]==benchMark[dp[j]-1]) count++;
                    if(j>=w3&&dp[j-w3]>0) if(benchMark[dp[j-w3]-1]==counts[dp[j-w3]-1]--) count--;
                    if(count==cs.size()) result.add(j-w3+w2);
                }
            }        
            return result;
        }
    }
    

Log in to reply
 

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