Substring with Concatenation of

Substring with Concatenation of All Words

题目描述

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

Example 1:

Input:
  s = "barfoothefoobarman",
  words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoor" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.
Example 2:

Input:
  s = "wordgoodstudentgoodword",
  words = ["word","student"]
Output: []

思路：

• 题的特点是被匹配字串都是等长的。所以才能将子串的单词子串，易于用哈希O(1)查找。
• 匹配集合用哈希表计数。遍历子串及子串的单词子串，存在则加入已匹配哈希。
• 这些情况放弃当前子串匹配：单词子串匹配次数超出，单词子串不匹配。

细节：

• 输入条件检查： if s == "" || len(words) == 0{return nil}
• 哈希表put需要判断，所以多写了几行代码。

解：

package main

import "fmt"

func findSubstring(s string, words []string) []int {
    if s == "" || len(words) == 0{return nil}
    res := make([]int,0,len(s))
    sSlice := []rune(s)
    wordsMap := make(map[string]int, len(words))
    lenWord := len(words[0])
    lenSubstr := lenWord * len(words)
    for _, elem := range words {
        _, ok := wordsMap[elem]
        if ok {
            wordsMap[elem] = wordsMap[elem] + 1
        } else {
            wordsMap[elem] = 1
        }
    }
    for i := 0; i <= len(s)-lenSubstr; i++ {
        subMap := make(map[string]int,len(words))
        j :=0
        for ;j<len(words);j++ {
            subStr := string(sSlice[i+j*lenWord:i+j*lenWord+lenWord])
            if num,ok := wordsMap[subStr];ok {
                if numSub,ok := subMap[subStr];ok{
                    subMap[subStr] = numSub+1
                    if numSub+1 > num {
                        break
                    }
                }else {
                    subMap[subStr] = 1
                }
            } else {
                break
            }
        }
        if j == len(words) {
            res = append(res,i)
        }
    }
    if len(res) == 0 {return nil}
    return res
}

func main()  {
    s := "aaaaaaaa"
    words := []string{"aa","aa","aa"}
    res := findSubstring(s,words)
    fmt.Print(res)
}