给定一个字符串 str 和一个字符串数组 words。 words 中所有字符串长度相同。 str 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。 例如,如果 words = ["ab","cd","ef"], 那么 "abcdef", "abefcd","cdabef", "cdefab","efabcd", 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串,因为他不是任何 words 排列的连接。 请找到所有串联字符串在 str 中的开始索引,最终结果以int数组形式,索引按照从小大到的顺序返回。
时间: 2023-07-08 13:45:21 浏览: 73
这是一道经典的字符串匹配问题,可以使用滑动窗口和哈希表来解决。具体思路如下:
1.将 words 中的所有字符串存入一个哈希表中,哈希表的键是每个字符串,值是该字符串出现的次数。
2.枚举 str 中所有可能的子串作为串联子串的起点。具体做法是每次向右移动一个单词的长度,枚举所有可能的起点。
3.对于每个起点,判断以该起点为起点的子串是否是一个串联子串。具体做法是从起点开始,每次向右移动一个单词的长度,将移动到的单词从哈希表中减去一次出现次数,直到所有单词都被匹配到或者存在不匹配的单词。如果所有单词都被匹配到,则说明该子串是一个串联子串,记录该子串的起点索引。
4.返回所有匹配到的子串的起点索引。
代码如下:
相关问题
给定一个字符串,输出所有长度至少为2的回文子串
这是一个编码过的问题,需要先将其解码。解码后的问题为:给定一个字符串,输出所有长度至少为2的回文子串。
解决问题的话可以使用两种方法,一种是暴力枚举所有可能的子串,然后判断是否为回文子串,时间复杂度为O(n^3)。另一种是使用Manacher算法,时间复杂度为O(n)。
python给定一个字符串,输出所有长度至少为2的回文子串。
可以使用中心扩展算法来解决这个问题。具体步骤如下:
1. 遍历字符串,以每个字符为中心,向两边扩展,找到所有以该字符为中心的回文子串。
2. 遍历字符串,以每两个相邻字符的中心,向两边扩展,找到所有以这两个字符为中心的回文子串。
3. 将步骤1和步骤2找到的所有回文子串合并去重,输出结果。
以下是实现代码:
def find_palindromic_substrings(s):
res = set()
for i in range(len(s)):
# 以单个字符为中心的回文子串
l, r = i, i
while l >= 0 and r < len(s) and s[l] == s[r]:
res.add(s[l:r+1])
l -= 1
r += 1
# 以相邻两个字符为中心的回文子串
l, r = i, i+1
while l >= 0 and r < len(s) and s[l] == s[r]:
res.add(s[l:r+1])
l -= 1
r += 1
return list(res)
s = "abcbadefg"
print(find_palindromic_substrings(s)) # ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'bc', 'cb', 'badab', 'def', 'aba']
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)