leetcode30:串联全部单词的字串

给定一个字符串 s 和一个字符串数组 words。 words 中全部字符串 长度类似。
 s 中的 串联子串 是指一个包罗  words 中全部字符串以恣意序次分列毗连起来的子串。

• 比方，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，由于他不是任何 words 分列的毗连。
  

返回全部串联子串在 s 中的开始索引。你可以以 恣意序次 返复兴案。

示例 1：

2. <strong>输入：</strong>s = "barfoothefoobarman", words = ["foo","bar"]
3. <strong>输出：</strong>[0,9]
4. <strong>解释：</strong>因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
5. 子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
6. 子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
7. 输出顺序无关紧要。返回 [9,0] 也是可以的。

复制代码

示例 2：

2. <strong>输入：</strong>s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
3. <strong>输出：</strong>[]
4. <strong>解释：</strong>因为<strong> </strong>words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
5. s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
6. 所以我们返回一个空数组。

复制代码

示例 3：

2. <strong>输入：</strong>s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
3. <strong>输出：</strong>[6,9,12]
4. <strong>解释：</strong>因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。
5. 子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。
6. 子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。
7. 子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。

复制代码

提示：

• 1 <= s.length <= 104
  
• 1 <= words.length <= 5000
  
• 1 <= words.length <= 30
  
• words 和 s 由小写英笔墨母构成
  

本题要求在字符串 s 中找到全部包罗字符串数组 words 中全部单词的串联子串的起始索引，words 中单词的序次可以恣意分列，但必须紧挨着出现在子串中。
步调1：标题分析

• s 是一个字符串，words 是一个包罗多个字符串的数组，这些字符串的长度类似。
  
• 我们须要在字符串 s 中找到全部子串，这些子串由 words 中的单词全部串联而成。
  
• 利用滑动窗口方法来高效地找到全部满意条件的子串。
  

步调2：算法筹划与步调分解
解题思绪

•         变量初始化
  
  
  
  • 获取 inputString 的长度 inputLength，wordList 的单词数量 wordCount，每个单词的长度 wordLength，以及全部单词拼接后的总长度 totalWordsLength。
    
  • 如果 inputString 的长度小于 totalWordsLength，则没有大概的结果，直接返回空向量。
    
  
  
•         词频统计
  
  
  
  • 利用哈希表 wordFrequencyMap 统计 wordList 中各个单词的出现次数，以便在后续判定子串中的单词是否符合要求。
    
  
  
•         滑动窗口遍历
  
  
  
  • 对字符串 inputString 的全部大概的出发点举行遍历（从 0 到 wordLength - 1），从差别出发点来举行窗口滑动，确保覆盖全部大概的位置。
    
  • 对每一个大概的出发点，利用左右指针 (leftPointer 和 rightPointer) 实现滑动窗口，窗口的长度为 wordLength 的整数倍。
    
  • 窗口逻辑：
    
    
    
    • 利用右指针 rightPointer 遍历字符串，每次获取当前窗口中的单词。
      
    • 如果当前单词在 wordList 中存在，则更新当前窗口的单词频率 currentWindowFrequencyMap。
      
    • 如果窗口中某个单词的频率超出了 wordFrequencyMap 中的值，则利用左指针 leftPointer 移动窗口，直到频率符合要求。
      
    • 当窗口内的单词数量便是 wordList 中的单词数量时，纪录当前左指针位置为结果索引。
      
    • 如果碰到一个无效的单词（不在 wordList 中），则清空窗口的频率统计，并将左指针直接移动到下一个位置。
      
    
    
  
  
•         复杂度分析
  
  
  
  • 时间复杂度：
    
    
    
    • 滑动窗口的出发点有 wordLength 种大概，每次滑动时右指针从左到右遍历整个字符串，因此时间复杂度为 O(wordLength * (inputLength / wordLength))，即 O(inputLength)。
      
    • 在窗口滑动过程中，每次插入和查找利用的时间复杂度为 O(1)，因此团体时间复杂度为 O(inputLength)。
      
    
    
  • 空间复杂度：
    
    
    
    • 利用了两个哈希表来纪录词频信息，空间复杂度为 O(wordCount)，此中 wordCount 是 wordList 的巨细。
      
    
    
  
  

步调3：c++代码

步调4：算法优化与服从提拔的开导

•         滑动窗口的利用：
  
  
  
  • 这种滑动窗口加哈希表的方法可以有用镌汰重复盘算，尤其是当窗口向右滑动时，不须要完全重新统计每个单词，只须要更新窗口内的变革。
    
  • 在大规模数据处理惩罚时，滑动窗口是一种非常有用的技能，用于在给定窗口内不绝更新盘算。
    
  
  
•         哈希表的快速查找：
  
  
  
  • 利用哈希表存储词频，可以在 O(1) 的时间内查找单词的出现次数，这极大地进步了匹配的服从。
    
  • 通过词频统计，可以轻松处理惩罚包罗重复单词的环境。
    
  
  
•         优化潜力：
  
  
  
  • 如果 words 中有较多重复单词，大概可以进一步优化数据布局，比方利用自界说的计数器类来镌汰哈希表查找的开销。
    
  • 如果 words 中单词长度较长，可以思量利用字符串哈希或其他方法来优化字符串匹配的服从。
    
  
  

步调5：实际应用场景分析

实际应用示例：日志分析和关键字检测：

• 场景：
  
  
  
  • 在日志分析中，我们大概须要检测体系日志中的特定模式，确保某些关键字以某种序次或组合出现，比方检测网络攻击模式、用户运动分析等。
    
  
  
• 实现方法：
  
  
  
  • 可以将体系日志作为字符串 s，而 words 则是须要检测的关键字列表。利用上述算法，我们可以快速找出哪些位置出现了全部关键字的组合，这对日志监控、入侵检测等非常有用。
    
  • 在实际中，这种方式可以被嵌入到主动化监控体系中，一连对及时日志举行分析，以便及时发现非常模式和埋伏威胁。
    
  
  

通过上述步调，我们不但办理了一个算法标题，还展示了怎样将这种算法应用到实际生存中，从而优化服从、提拔生产力。在类似的应用中，处理惩罚大规模字符串匹配和检测，团结滑动窗口、哈希表等高效算法是一个有用的方案。