Ricky.L的随笔
0%

LeetCode.30.串联所有单词的子串（困难）

发表于 更新于 分类于 Disqus：

题目

LeetCode.30.串联所有单词的子串（困难）

给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符 ，但不需要考虑 words 中单词串联的顺序。

题解

暴力推导

  1. 穷举出所有s可能的子串。
  2. 对每个子串检查能不能拿words中所有单词串联得出。

穷举出所有s可能的子串，有什么优化？

题目要求恰好可以用words中所有单词串联形成的子串，所以子串的长度是确定的，只要穷举这个特定长度所有子串就行了，不需要穷举所有长度的子串。

其实这就相当于弄一个滑动窗口依次检测。

怎么检查子串能不能拿words中所有单词串联得出？

按道理得组合所有words中单词的情况。

但是题目说所有单词长度相同，假设长度为n，可以把大子串再分割成m分长度为n的小子串，看小子串是不是在words里。

检查一个东西是不是在某个集合里，可以想到用哈希表，用O(1)时间查询得出结果。

但是哈希表不能存储相同的单词，所以要给重复出现的单词计数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    fun findSubstring(s: String, words: Array<String>): List<Int> {
        if (words.isEmpty()) return emptyList()
        val result = mutableListOf<Int>()
        val wordCount = words.size
        // 每个单词的长度
        val wordLength = words.first().length
        // 生成哈希表：记录每个单词有多少个
        val allWords = words.groupingBy { it }.eachCount()
        // 穷举所有可能的子串
        for (i in 0..(s.length - wordCount * wordLength)) {
            val countMap = mutableMapOf<String, Int>()
            var j = 0
            while (j < wordCount) {
	            // 子串按单词长度切片，检查每一片是否在单词列表里
                val word = s.substring(i + j * wordLength, i + (j + 1) * wordLength)
                if (allWords.containsKey(word)) {
                    // 注意对重复单词计数，单词在子串中出现过的次数与在words出现的次数应该一致
                    val count = countMap.getOrDefault(word, 0)
                    countMap[word] = count + 1
                    if (countMap[word]!! > allWords[word]!!) {
                        break
                    }
                } else break
                j++
            }
            if (j == wordCount) {
                result.add(i)
            }
        }
        return result
    }
}

时间复杂度O(mn)：
假设字符串s长度为m，滑动窗口穿过整个s，最坏情况下滑动窗口大小为1，需要移动m次。
判断每个滑动窗口的子串是不是能由words所有单词组成，最坏情况需要遍历words所有单词，假设words长度为n，就就要遍历n次。

空间复杂度O(n)：
用哈希表记录words中所有单词出现的次数。