leetcode_30. 串联所有单词的子串
题目思路分析1代码展示1思路分析2代码展示2
题目
leetcode题目链接
思路分析1
题目要求：找出 由words数组组成的字符串（每一个元素word等长），在字符转s中的位置
数组words生成的字典dic2遍历字符串，从头开始判断长度为lenwords的字符串 生成的字典dic1如果dic1 与 dic2 相同，说明找到
代码展示1
def findSubstring(self
, s
: str, words
):
if s
=="" or words
==[]:
return[]
res
=[]
lenwords
= len(words
[0]*len(words
))
dic2
= self
.help2
(words
)
for i
in range(len(s
)-lenwords
+1):
dic1
= self
.help1
(s
[i
:i
+lenwords
],len(words
[0]))
if dic1
==dic2
:
res
.append
(i
)
return res
def help1(self
,str,interval
):
dic
= {}
for i
in range(0,len(str)-interval
+1,interval
):
if str[i
:i
+interval
] not in dic
:
dic
[str[i
:i
+interval
]] = 1
else:
dic
[str[i
:i
+interval
]] += 1
return dic
def help2(self
,words
):
dic
={}
for i
in words
:
if i
not in dic
:
dic
[i
] = 1
else:
dic
[i
] += 1
return dic
思路分析2
题目要求：找出 由words数组组成的字符串（每一个元素word等长），在字符转s中的位置
对数组words排序遍历字符串，对长度为totallen的字符串，拆成数组，排序如果 排好序的数组 相同，说明找到
代码展示2
def findSubstring2(self
, s
: str, words
):
if s
=="" or words
==[]:
return[]
res
=[]
words
= sorted(words
)
totallen
= len(words
[0])*len(words
)
wordlen
= len(words
[0])
for i
in range(len(s
)-totallen
+1):
temp
= []
for j
in range(0,totallen
,wordlen
):
temp
.append
(s
[i
+j
:i
+j
+wordlen
])
temp
= sorted(temp
)
if temp
== words
:
res
.append
(i
)
return res
