JAVA 20 ms solution with comments


  • 0
    D

    idea is use hashmap and slide window.
    the single word's length is k , than we have k kinds of windows.
    for each kind of window, we slide it right k length
    if find a new word not belongs to dictionary, then put start at it's right and clean the hashmap COPY

    public List<Integer> findSubstring(String s, String[] L) {
        List<Integer> list = new ArrayList<Integer>();
    	if(s==null|| s==""||L==null||L[0].length()==0)
    		return list;
    	HashMap<String, Integer> map = new   HashMap<String ,Integer>();
    	int len=L[0].length();
    	int k = len;
    	int count = L.length;
    	for (String  tmp : L) {
    		if(!map.containsKey(tmp)) {
    			map.put(tmp, 1);
    		}else
    		    map.put(tmp,map.get(tmp)+1);
    	}
    	
    	String curr = "";
    	int start = 0;
    	int x = 0;
    	for (int i = 0; i <k; i++) {      // there are k kind of slide window, and slide right k each time
    		HashMap<String , Integer> copy = new HashMap<>();
    		start = i;
    		for(int j =i; j+k<=s.length(); j = j + k ){     // slide window, the window's length is k*count
    		    curr = s.substring(j,j+k);
    		    if(map.containsKey(curr)){      //curr belongs to dictionary
    		        addright(copy,curr);
    		        if(j+k - start > k*count){      // window size exceed k*count
    		            removeleft(copy,  s.substring(start,start+k));
    		            start = start + k;
    		        }
    		        if(j+k-start == k*count && copy.equals(map))
    		            list.add(start);
    		    }else{          // dictionary don't include curr, skip it
    		        
    		        copy.clear();
    		        start = j + k;
    		    }
    		}
    	}
        return list;
    
    }
    
    public void addright(HashMap<String,Integer> copy, String curr){
    		if(copy.containsKey(curr)){        // curr l in copy
    		    copy.put(curr,copy.get(curr)+1);
    		}else{      // curr do not exist in copy, but it belongs to dictionary
    		    copy.put(curr,1);
    	    }
    }
    
    public void removeleft(HashMap<String,Integer> copy, String curr){
        int x = copy.get(curr);
        if(x==1)   copy.remove(curr);
        else    copy.put(curr,x-1);
    }

Log in to reply
 

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