[Leetcode][Python]30: Substring with Concatenation of All Words

# -*- coding: utf8 -*-
'''
__author__ = 'dabay.wang@gmail.com'
30: Substring with Concatenation of All Words
https://oj.leetcode.com/problems/substring-with-concatenation-of-all-words/
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). ===Comments by Dabay=== 生成一个hash表来记录每个词在L中出现的次数。
扫描要检查的字符串S,检查以这个字母开始的 长度为L总长度 的字符串,
如果小词在hash表中,值减一;如果最后每一个hash值都是0,说明正好全部匹配完,加入到结果。
重新初始化hash表,进行下一次检查。
''' class Solution:
# @param S, a string
# @param L, a list of string
# @return a list of integer
def findSubstring(self, S, L):
d = {}
for x in L:
if x not in d:
d[x] = 1
else:
d[x] += 1
res = []
word_length = len(L[0])
i = 0
while i < len(S) - word_length * len(L) + 1:
j = i
dd = dict(d)
while j < i + word_length * len(L):
word = S[j:j+word_length]
if word in dd:
dd[word] -= 1
if dd[word] < 0:
break
else:
break
j += word_length
else:
res.append(i)
i += 1
return res def main():
s = Solution()
string = "aaa"
dictionary = ["a", "b"]
print s.findSubstring(string, dictionary) if __name__ == "__main__":
import time
start = time.clock()
main()
print "%s sec" % (time.clock() - start)
上一篇:Use Generic Replacements of 1.X Framework API Classes 用泛型替换Framework 1.X版本的API类


下一篇:Maven中基于POM.xml的Profile来动态切换配置信息