19ms in golang


  • 0
    M

    maybe too long code, but run fast

    func findSubstring(s string, words []string) []int {
    	res := []int{}
    	wordLen := len(words[0])
    	//build tartgetMap
    	targetMap := make(map[string]int)
    	for _, v := range words {
    		targetMap[v] ++
    	}
    	//we loop from 0 to m-1, that's all possible start point
    	for i := 0; i < wordLen; i++ {
    		wordMap := make(map[string]int)
    		//left and right build the match window
    		left := i
    		right := left
    		//use a count to get the word matched
    		count := 0
    		//if we get a word in words which make the total count overflow, that's a badStr
    		badStr := ""
    		//left loop to end
    		for left < len(s) - wordLen * len(words) + 1 {
    			//right loop to end
    			for right < len(s) {
    				//right step by wordLen to end
    				if right + wordLen <= len(s) {
    					substr := s[right:right + wordLen]
    					//if the substr is in words
    					if targetMap[substr] != 0 {
    						//update the wordMap
    						wordMap[substr]++
    						right = right + wordLen
    						//is substr a bad match?
    						if wordMap[substr] <= targetMap[substr] {
    							//go on and test count
    							count++
    							if count == len(words) {
    								res = append(res, left)
    								//left go forward
    								str1 := s[left:left + wordLen]
    								left = left + wordLen
    								wordMap[str1]--
    								count--
    							} else {
    								continue
    							}
    						} else {
    							//jump out
    							badStr = substr
    							break
    						}
    					} else {
    						//we get a word not in words, so jump to right + wordLen
    						left = right + wordLen
    						right = left
    						wordMap = make(map[string]int)
    						count = 0
    					}
    				} else {
    					break
    				}
    			}
    			//if we meet a badStr, left go forward until we meet another badStr
    			if badStr != "" {
    				for left + wordLen <= len(s) {
    					substr := s[left:left + wordLen]
    					wordMap[substr]--
    					left = left + wordLen
    					if substr == badStr {
    						break
    					} else {
    						count--
    					}
    				}
    				if left + wordLen > len(s) {
    					break
    				}
    			} else {
    				break
    			}
    		}
    	}
    	return res
    }
    
    

Log in to reply
 

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