给定一个字符串 str 和一个字符串数组 words。 words 中所有字符串长度相同。 str 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。 例如,如果 words = ["ab","cd","ef"], 那么 "abcdef", "abefcd","cdabef", "cdefab","efabcd", 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串,因为他不是任何 words 排列的连接。 请找到所有串联字符串在 str 中的开始索引,最终结果以int数组形式,索引按照从小大到的顺序返回。
时间: 2023-07-08 14:45:21 浏览: 111
输出一个字符串的全部子串.docx
这是一道经典的字符串匹配问题,可以使用滑动窗口和哈希表来解决。具体思路如下:
1.将 words 中的所有字符串存入一个哈希表中,哈希表的键是每个字符串,值是该字符串出现的次数。
2.枚举 str 中所有可能的子串作为串联子串的起点。具体做法是每次向右移动一个单词的长度,枚举所有可能的起点。
3.对于每个起点,判断以该起点为起点的子串是否是一个串联子串。具体做法是从起点开始,每次向右移动一个单词的长度,将移动到的单词从哈希表中减去一次出现次数,直到所有单词都被匹配到或者存在不匹配的单词。如果所有单词都被匹配到,则说明该子串是一个串联子串,记录该子串的起点索引。
4.返回所有匹配到的子串的起点索引。
代码如下:
阅读全文