Lever's Castle

30. 串联所有单词的子串

April 14, 2020

https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/

解:

func findSubstring(s string, words []string) []int {
    var result []int
    if len(s) == 0 || len(words) == 0 {
        return result
    }
    wordMap := generateWordMap(words)
    start := -1
    stepSize := len(words[0])
    i := 0
    wordCount := 0
    for i < len(s) {
        if i+stepSize > len(s) {
            if start > -1 {
                i = start + 1
                start = -1
                wordMap = generateWordMap(words)
                wordCount = 0
                continue
            } else {
                break
            }
        }
        subStr := string(s[i:i+stepSize])
        if wordMap[subStr] > 0 {
            wordMap[subStr]--
            wordCount++
            if start == -1 {
                start = i
            }
            i += stepSize
        } else if start == -1 {
            i++
        } else {
            i = start + 1
            wordMap = generateWordMap(words)
            start = -1
            wordCount = 0
        }
        if wordCount == len(words) {
            result = append(result, start)
            i = start + 1
            wordMap = generateWordMap(words)
            start = -1
            wordCount = 0
        }
    }

    return result
}

func generateWordMap(words []string) (wordMap map[string]int) {
    wordMap = make(map[string]int)
    for _, word := range words {
        wordMap[word] = wordMap[word] + 1
    }
    return wordMap
}

题目其实并不难,就是实现上会比较绕,只要有一个清晰的思路,写下去就不会有问题。这里我说下我的思路,很简单,就是遍历字符串 s,对 s 按照样本字符串的长度进行切片,并从样本字符串中确认该子串是否存在,存在就继续向后找,不存在则重新找到头重新划切片。

因为要找到样本字符串中是否有子串,所以我先构造了一个 map 结构,而样本字符串可能存在同一个字符串出现多次的情况,所以 map 的值我用字符串出现的次数来填充。在遍历的过程中,访问到过一次,就减一,以确保数量能对上。而一旦本轮匹配失败,就需要重置这个匹配计数器。

这里先想好什么是一轮成功的匹配:从某个开始位置进行切片,从这个位置开始连续 n 次匹配到 wordMap 中的字符串,并且最终 n == len(words),则此为一轮成功的匹配,此开始位置也是一个成功解。那么很自然,不成功的匹配首先一定是子串在 wordMap 中没找到。而在不成功的场景中,也需要分是开始就不成功还是匹配了一部分之后的不成功。这里涉及到对 i 的处理。不成功的场景也要对各种计量值进行重置,以免影响下次匹配。


Lever

痕迹
没有过去,就没法认定现在的自己