链接

Substring with Concatenation of All Words

难度

Hard

描述

给定一个字符串s作为母串，和一系列长度相等的字符串words，要求返回s当中所有的位置，使得从该位置开始可以找到所有的words，并且所有的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.

样例 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.

样例 2:

Input:
  s =  "wordgoodgoodgoodbestword",
words = ["word","good","best","word"]
Output: []

题解

这道题的难度是Hard，老实讲的确不简单，尤其是如果在面试当中被问到，恐怕很难一下想出最佳答案。

暴力

还是老规矩，我们退而求其次，忘了最佳答案这茬，先想出简单的方法再来思考怎么优化。最简单的方法当然是暴力，我们首先遍历所有的起始位置，然后后面一个单词一个单词的匹配。如果成功匹配就记录答案，失败的话则继续搜索下一个位置。

这么做看起来没有问题，但是一些细节需要注意。比如题目当中只说单词的长度一样，并没有说单词会不会重复。显然我们应该考虑单词出现重复的情况，既然要考虑单词出现重复，那么就不能用一个set来记录单词是否出现过，而是需要统计每个单词出现的个数。其次，我们在遍历的时候，也一样，也需要统计当前匹配到的单词的数量。

这道题暴力的思路还是比较清晰的，代码也不难写：

class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:
        n = len(s)
# 单词不存在直接返回
if len(words) == :
return []

        ret = []
        word_cnt = len(words)
        m = len(words[])
        words_dict = {}
# 初始化，记录词表
for word in words:
            words_dict[word] = words_dict.get(word, ) + 1

# 枚举开始的位置
for i in range(n):
            cur_dict = {}
            matched = 
# 每次遍历一个单词
for start in range(i, n, m):
                w = s[start: start+m]
# 如果单词存在，并且当前匹配的数量小于目标，则进行记录
if w in words_dict and cur_dict.get(w, ) < words_dict[w]:
                    cur_dict[w] = cur_dict.get(w, ) + 1
                    matched += 1
else:
break
# 所有单词已经匹配
if matched == word_cnt:
                    ret.append(i)
break
return ret

Two pointers

1. ...[1][2][3]....[1][2][3]....，这种情况最容易想到。在一个正确答案后面一段距离之后还有另一个正确答案，由于我们每次找到正确答案就退出了，所以又需要遍历很多次才可以找到下一个答案。
2. ....[1][2][1][2][3]....，这种情况当中，我们在找到了前面第一个错误的[1][2]之后，由于发现不对，所以退出了循环。接下来我们要遍历2m次（单词长度为m），才可以找到[1][2][3]这个答案。要是当时我们可以将错就错继续往下搜索，就可以直接找到答案了。

优化1

优化2

class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:
        n = len(s)
if len(words) == :
return []

# 初始化的部分和之前一样
        ret = []
        word_cnt = len(words)
        m = len(words[])
        words_dict = {}
for word in words:
            words_dict[word] = words_dict.get(word, ) + 1

# 只遍历[0, m)
for i in range(m):
            cur_dict = {}
# l和r表示当前的区间两侧端点
            l = i
            matched = 
for r in range(i, n, m):
# 获取当前的单词
                word = s[r: r+m]
# 如果单词不在词库当中，清空之前的数据
if word not in words_dict:
# l赋值成下一个开始的r
                    l = r + m
# 所有匹配记录清空
                    matched = 
                    cur_dict = {}
continue
# 记录单词
                cur_dict[word] = cur_dict.get(word, ) + 1
                matched += 1
# 如果数量超界的话，就弹出左侧
while cur_dict[word] > words_dict[word]:
                    w = s[l: l+m]
                    cur_dict[w] -= 1
                    matched -= 1
                    l += m
# 如果匹配数量一致，则记录答案，也就是l的位置
if matched == word_cnt:
                    ret.append(l)
return ret