You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.
For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]
You should return the indices: [0,9].
(order does not matter).
题目简述：
主字符串S，模式字符串list：L（L中的元素等长，有可能重复），寻找L以任意顺序拼接后得到的字符串在S中的索引。
解题思路：
1. 遍历L中的模式串，建立字典树trie，叶子节点保存模式串的唯一编号num（从1开始），以及该模式串的个数val；并记录不重复模式串的个数tt
2. 遍历母串S，使用字典树生成数组arr，其中arr[i]保存从母串位置i开始匹配到的模式串唯一编号num与该模式串在L中的个数val的元组(num, val)。如果arr[i]为(0, 0)，则表示在母串位置i没有匹配到L中的任何模式串。例如样例中生成的arr = [(2, 1), (0, 0), (0, 0), (1, 1), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (1, 1), (0, 0), (0, 0), (2, 1), (0, 0), (0, 0), (0, 0)]
3. 遍历母串S，采用“滑动窗口法”。数组元素dp[i]保存元组( wordDict , wordSet , accm )：（1）模式串字典wordDict（key为模式串唯一编号num，value为模式串在窗口内的出现次数），（2）出现次数足够的模式串集合wordSet，（3）连续出现的模式串个数accm
Python代码：
class Solution:
def buildTrie(self, L):
trie = {}
t = 0
for word in L:
node = trie
for letter in word:
child = node.get(letter)
if child is None:
child = {}
node[letter] = child
node = child
val = node.get('val', 0)
if val == 0:
t += 1
node['num'] = t
node['val'] = val + 1
return (trie, t)
def valTrie(self, string, start, size, trie):
node = trie
for i in range(start, start + size):
if node.get(string[i]) is None:
return (0, 0) # string[start : start + size] not in trie
node = node[string[i]]
return (node['num'], node['val'])
def findSubstring(self, S, L):
lenL = len(L)
size = len(L[0])
trie, tt = self.buildTrie(L)
strlen = len(S)
arr = []
for i in range(strlen - size + 1):
arr.append(self.valTrie(S, i, size, trie))
result = []
dp = []
for i in range(strlen - size + 1):
wordDict = None
wordSet = set()
accm = 0
if arr[i][0] > 0:
idx = i - size * (lenL - 1)
if i < size:
wordDict = {arr[i][0] : 1}
if arr[i][1] == 1:
wordSet.add(arr[i][0])
if len(wordSet) == tt:
result.append(i)
else:
wordDict, wordSet, accm = dp[i - size]
if wordDict is None:
wordDict = {}
accm += 1
num = wordDict.get(arr[i][0], 0)
wordDict[arr[i][0]] = num + 1
if num + 1 >= arr[i][1]:
wordSet.add(arr[i][0])
if idx >= 0:
if len(wordSet) == tt:
result.append(idx)
if accm >= lenL - 1 and arr[idx][0] > 0:
num = wordDict.get(arr[idx][0], 0)
if num - 1 < arr[idx][1] and arr[idx][0] in wordSet:
wordSet.remove(arr[idx][0])
if num >= 1:
wordDict[arr[idx][0]] = num - 1
dp.append((wordDict,wordSet,accm))
return result
Judge评测结果：Accepted 704ms
本文链接：http://bookshadow.com/weblog/2014/04/24/leetcode-substring-concatenation-all-words/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。
捐赠书影博客
