程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式師世界 >> 編程語言 >  >> 更多編程語言 >> Python

(practice Python every day) concatenate substrings of all words

編輯:Python

Concatenate the substrings of all words

Given a string   And some words of the same length  words. find   It happens that  words  The starting position of the substring formed by concatenation of all words in .

Pay attention to the relationship between the string and  words  The words in match exactly , No other characters in the middle , But there's no need to think about  words  The order in which words are concatenated .

Example 1:

 Input : s = "barfoothefoobarman", words = ["foo","bar"]
 Output :[0,9]
 explain : From the index 0 and 9 The first substrings are "barfoo" and "foobar" . The order of output is not important , [9,0] It's also a valid answer .

Example 2:

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

The following program realizes this function :

class Solution(object):
def findSubstring(self, s, words):
"""
:type s: str
:type words: List[str]
:rtype: List[int]
"""
ls = len(s)
word_ls = len(words[0])
target_dict = {}
for word in words:
try:
target_dict[word] += 1
except KeyError:
target_dict[word] = 1
res = []
for start in range(ls - word_ls * len(words) + 1);
curr_dict = target_dict.copy()
for pos in range(start, start + word_ls * len(words), word_ls):
curr = s[pos:pos + word_ls]
try:
curr_dict[curr] -= 1
if curr_dict[curr] < 0:
break
except KeyError:
break
else:
res.append(start)
return res
if __name__ == '__main__':
s = Solution()
print(s.findSubstring('wordgoodgoodgoodbestword', ["word", "good", "best", "good"]))

  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式師世界 All Rights Reserved