對(duì)于這道題凌箕,理解題意很重要袜蚕,要考慮到words中出現(xiàn)重復(fù)單詞的情況遭顶。并且,要求找出所有的可能的index(包括重疊可能),舉個(gè)例子汪诉,如果
s='abcdefcd'
,words=['cd', 'ef']
,那么應(yīng)返回[2, 4]
睬辐。用了好幾種方案,都不能解決問題宾肺。最后的解題思路是:假設(shè)word長度為
length
溯饵,個(gè)數(shù)是n
,從索引x=0
開始锨用,如果s[x:x+length]
是words中一員丰刊,那么從x
開始從s中截取所有words拼接長度的字符串ss=s[x:x+length*n]
,在函數(shù)isValid
中判斷該子串是否是所有words
的拼接增拥,如果是則記錄索引啄巧。在isValid
中的判斷思路是,根據(jù)word
長度掌栅,將ss
劃分成list列表words_ss
秩仆,然后遍歷words
,每遍歷一個(gè)word
猾封,判斷words_ss
中有無此word
澄耍,若無,直接返回False
晌缘;若有齐莲,則從word_ss
中刪除該word
。遍歷結(jié)束磷箕,返回True
选酗。
class Solution(object):
def findSubstring(self, s, words):
"""
:type s: str
:type words: List[str]
:rtype: List[int]
"""
if len(words) == 0:
return []
length = len(words[0])
if length > len(s):
return []
count_c = len(words) * length
res = []
i = 0
while i < len(s) - count_c + 1:
word = s[i:i + length]
if word in words:
ss = s[i:i + count_c]
if self.isValid(ss, words, length):
res.append(i)
i += 1
else:
i += 1
return res
def isValid(self, ss, words, length):
words_ss = []
for x in xrange(len(ss) / length):
word = ss[x * length:(x + 1) * length]
words_ss.append(word)
for word in words:
if word in words_ss:
words_ss.remove(word)
else:
return False
return True