030_串联所有单词的子串

Description

给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。 注意子串要与 words 中的单词完全匹配,中间不能有其他字符,但不需要考虑 words 中单词串联的顺序。

Example
输入:
  s = "barfoothefoobarman",
  words = ["foo","bar"]
输出:[0,9]
解释:
从索引 0 和 9 开始的子串分别是 "barfoor" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。

输入:
  s = "wordgoodgoodgoodbestword",
  words = ["word","good","best","word"]
输出:[]
Solution
//最优解?????//TODO
func findSubstring1(s string, words []string)(ret []int)  {
    if len(words) == 0 {return}
    wl := len(words[0])
    for off :=0;off < wl; off ++ {
        beg,end := off,off
        list := append(make([]string,0),words...)
        loop:
            for end+wl <= len(s) {
                for i ,v := range list{
                    if v == s[end:end+wl] {
                        end +=wl
                        list = append(list[:i],list[i+1:]...)
                        if len(list) == 0{
                            ret = append(ret,beg)
                        }
                        goto loop
                    }
                }
                if beg < end{
                    list = append(list,s[beg:beg+wl])
                }else {
                    end += wl
                }
                beg +=wl
            }
    }
    return
}

//暴力
func findSubstring(s string, words []string)(ret []int)  {
    if len(words) == 0 {
        return
    }

    wLen := len(words[0])

    left := 0
loop:
    beg ,end := left,left
    list := append(make([]string, 0), words...)
loop1:
    for end+wLen <= len(s){
        for i,v := range list {
            if v == s[end:end+len(v)] {
                end +=len(v)
                list = append(list[:i],list[i+1:]...)
                if len(list) == 0 {
                    ret = append(ret,beg)
                    goto loop
                }else {
                    goto loop1
                }
            }
        }
        left++
        goto loop
    }
    return
}



//空间换时间
func findSubstring2(s string, words []string) []int {
    var ret  []int
    if len(words) == 0 || len(s) == 0 {
        return ret
    }
    l := len(words[0])
    size := l * len(words)
    if size > len(s) {
        return ret
    }
    idx := 0
    idxmap := make(map[string]int)
    for _, str := range words {
        _, ok := idxmap[str]
        if ok == false {
            idxmap[str] = idx
            idx++
        }
    }
    rawmap := make([]int, len(idxmap))
    for i := 0; i < len(rawmap); i++ {
        rawmap[i] = 0
    }
    for _, str := range words {
        rawmap[idxmap[str]]++
    }

    stridx := make([]int, len(s)-l+1)
    for i := 0; i < len(stridx); i++ {
        str := s[i : i+l]
        idx, ok := idxmap[str]
        if ok == false {
            stridx[i] = -1
        } else {
            stridx[i] = idx
        }
    }
    for i := 0; i < len(stridx); i++ {
        curmap := make([]int, len(rawmap))
        for i := 0; i < len(rawmap); i++ {
            curmap[i] = rawmap[i]
        }
        for j := 0; j < size && i+j < len(stridx); j += l {
            if stridx[i+j] == -1 || curmap[stridx[i+j]] == 0 {
                break
            } else {
                curmap[stridx[i+j]]--
            }
            if j == size-l {
                ret = append(ret, i)
            }
        }
    }
    return ret
}

leetCode地址