JAVA 20 ms solution with comments

  • 0

    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);
    	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
    		        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))
    		    }else{          // dictionary don't include curr, skip it
    		        start = j + k;
        return list;
    public void addright(HashMap<String,Integer> copy, String curr){
    		if(copy.containsKey(curr)){        // curr l in copy
    		}else{      // curr do not exist in copy, but it belongs to dictionary
    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.