Slide Window,Cleanest code.


  • 0
    // Slide window
    func findSubstring(s string, words []string) []int {
    	results := []int{}
    	length := len(words[0])
    	total := length * len(words)
    
    	counts := make(map[string]int)
    	for i := 0; i < len(words); i++ {
    		counts[words[i]]++
    	}
    
    	for start := 0; start < length; start++ {
    		seen := make(map[string]int)
    
    		// window[prev, next]
    
    		prev := start
    		for next := prev + length; next <= len(s); {
    			ss := s[next-length : next]
    			if seen[ss] < counts[ss] {
    				// OK, go on.
    				seen[ss]++
    				if next-prev == total {
    					results = append(results, prev)
    				}
    				next += length
    			} else {
    				// FAILED, slide window.
    				head := s[prev : prev+length]
    				seen[head]--
    				prev += length
    			}
    		}
    	}
    
    	return results
    }
    
    

Log in to reply
 

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