30. 串联所有单词的子串 C#实现
30. 串联所有单词的子串
困难
给定一个字符串 s
和一个字符串数组 words
。 words
中所有字符串 长度相同。
s
中的 串联子串 是指一个包含 words
中所有字符串以任意顺序排列连接起来的子串。
- 例如,如果
words = ["ab","cd","ef"]
, 那么"abcdef"
,"abefcd"
,"cdabef"
,"cdefab"
,"efabcd"
, 和"efcdab"
都是串联子串。"acdbef"
不是串联子串,因为他不是任何words
排列的连接。
返回所有串联子串在 s
中的开始索引。你可以以 任意顺序 返回答案。
示例 1:
输入:s = "barfoothefoobarman", words = ["foo","bar"]
输出:[0,9]
解释:因为 words.length == 2 同时 words[i].length == 3,连接的子字符串的长度必须为 6。
子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。
示例 2:
输入:s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出:[]
解释:因为 words.length == 4 并且 words[i].length == 4,所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。
示例 3:
输入:s = "barfoofoobarthefoobarman", words = ["bar","foo","the"] 输出:[6,9,12] 解释:因为 words.length == 3 并且 words[i].length == 3,所以串联子串的长度必须为 9。 子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。 子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。 子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。
提示:
1 <= s.length <= 104
1 <= words.length <= 5000
1 <= words[i].length <= 30
words[i]
和s
由小写英文字母组成
代码如下:
public class Solution {
public IList<int> FindSubstring(string s, string[] words) {
IList<int> result = new List<int>();
if (s == null || s.Length == 0 || words == null || words.Length == 0) return result;
int wordLength = words[0].Length;
int wordCount = words.Length;
int totalLength = wordLength * wordCount;
// 统计 words 中每个单词出现的次数
Dictionary<string, int> wordFrequency = new Dictionary<string, int>();
foreach (var word in words)
{
if (wordFrequency.ContainsKey(word))
wordFrequency[word]++;
else
wordFrequency[word] = 1;
}
// 从每个可能的起点开始(0 到 wordLength-1),使用滑动窗口
for (int i = 0; i < wordLength; i++)
{
int left = i;
int right = i;
int matchedWords = 0;
Dictionary<string, int> seenWords = new Dictionary<string, int>();
// 移动右指针遍历字符串
while (right + wordLength <= s.Length)
{
// 从字符串中取出一个单词
string word = s.Substring(right, wordLength);
right += wordLength;
// 检查当前单词是否在 wordFrequency 中
if (wordFrequency.ContainsKey(word))
{
// 更新 seenWords 中的计数
if (seenWords.ContainsKey(word))
seenWords[word]++;
else
seenWords[word] = 1;
matchedWords++;
// 如果当前单词的数量超过了所需数量,缩小窗口
while (seenWords[word] > wordFrequency[word])
{
string leftWord = s.Substring(left, wordLength);
seenWords[leftWord]--;
matchedWords--;
left += wordLength;
}
// 当窗口大小正好等于 totalLength 时,表示找到一个符合要求的子串
if (matchedWords == wordCount)
result.Add(left);
}
else
{
// 如果单词不在 words 中,重置窗口
seenWords.Clear();
matchedWords = 0;
left = right;
}
}
}
return result;
}
}