问题描述
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.
For example, given:
s: "barfoothefoobarman"
words: ["foo", "bar"]
You should return the indices:[0,9].
(order does not matter).
思路分析
//前面有一些弯路分析。
LeetCode上此题标注的难度是Hard，所以直接用暴力的方法应该无法满足时间限制。考虑到单词的长度是相同的（k），如果指针每次向后移动k位，那么之前的匹配结果在此次匹配时可以利用，例如
s = 'abacadabc'
words = ['a', 'b', 'c']
当匹配到s2时，发现‘aba’不满足要求（因为a的出现次数超过限制），但知道之前的‘ab’满足要求而且s[2]位置的‘a’也在words中，因此可以推出‘ba’是满足要求的，这样在s[0]位置开始而在s[2]匹配失效后，可以直接从s[3]继续进行下面的匹配，而不需再返回s[1]处重新开始；
当匹配到s5时，发现‘d’不在words中，因此匹配失效，那么下次应从s[6]位置重新开始匹配；
上面两条规律通过保证“s不回溯”来提高匹配效率。
然而这么做存在问题。考虑下面两个的例子：
s = 'aaaaaaaa'
words = ['aa', 'aa', 'aa']
由于words中可能存在重复的单词（尤其是单词全部相同的情况），指针每次向后移动k位会导致部分解的丢失，在上面例子中，如果每次向后移动2位，会丢失s[1]位置开始的匹配。
s =‘ababaab’
words = ['ab', 'ba', 'ba']
当匹配到s[2]（ab）处发现匹配失效但‘ab’在words中，从s[4]开始继续匹配，会丢失s[1]位置开始的匹配。
因此，直接采取指针每次向后移动k位的方法是错误的。但如果不能每次移动k位，那么就无法保证s不回溯，相当于暴力解题，我尝试了使用Hash的暴力解法，果然会"Time Limit Exceeded"。
然后我看到了九章算法中的解答。其精妙之处在于，它将任务分解为k种情况，考虑从[0, k-1]开始匹配，在每次匹配的时候，就可以保证不回溯。这种方法相当于暴力和技巧的结合。
AC代码
#encoding=utf-8
class Solution(object):
def findSubstring(self, s, words):
"""
:type s: str
:type words: List[str]
:rtype: List[int]
"""
result = []
m = len(s) #待匹配串的长度
n = len(words) #单词个数
if n == 0:
return result
k = len(words[0]) #单词长度
dic = {}
for word in words:
if dic.has_key(word):
dic[word] += 1
else:
dic[word] = 1
dup = {}
for begin in range(k):
w_used = 0 #记录已经使用的单词数
p1 = begin
p2 = p1 + k
while m - p1 + 1 >= n * k: #s剩余长度大于等于单词表各单词总长度
#匹配时控制单词的出现次数不超过限制，因此当w_used==n时，就是匹配成功了
if w_used == n:
result.append(p1)
if p2 > m + k + 1:
break
w = s[p2-k:p2]
if w in dic:
if w in dup and dup[w] != 0:
#超过单词次数限制，把p1移到已经匹配的第一个w之后
if dup[w] == dic[w]:
end = s.index(w, p1, p2)
for i in range(p1, end, k):
rmv = s[i:i+k]
dup[rmv] -= 1
w_used -= 1
p1 = end + k
p2 += k
else:
dup[w] += 1
w_used += 1
p2 += k
else:
dup[w] = 1
w_used += 1
p2 += k
else: #出现不在word里的单词
p1 = p2
p2 = p1 + k
dup.clear()
w_used = 0
return result
Runtime: 84 ms, which beats 89.72% of python submissions.
