30. Substring with Concatenation of All Words
leetcode hard
#array#csharp#hard#hash-table#leetcode#search#sliding-window#string#tree#two-pointers
Task
Вам дана строка s и массив строк-слов. Все строки слов имеют одинаковую длину.Объединенная строка — это строка, которая в точности содержит все строки любой перестановки объединенных слов.
Например, если слова = ["ab", "cd", "ef"], то "abcdef", "abefcd", "cdabef", "cdefab", "efabcd" и "efcdab" являются объединенными строками. «acdbef» не является объединенной строкой, поскольку не является объединением какой-либо перестановки слов.
Возвращает массив начальных индексов всех объединенных подстрок в s. Вы можете вернуть ответ в любом порядке.
C# solution
matched/originalpublic class Solution {
public IList<int> FindSubstring(string s, string[] words) {
var size = words[0].Length;
var window = size * words.Length;
var wordMap = new Dictionary<string, int[]>();
foreach (var word in words)
{
if (!wordMap.TryGetValue(word, out var map))
{
wordMap.Add(word, map = new int[2]);
}
map[0] += 1;
}
var checkMap = new List<(int index, string word)>();
for (var i = 0; i <= s.Length - size; i++)
{
var word = s[i..(i + size)];
if (wordMap.ContainsKey(word))
{
checkMap.Add((i, word));
}
}
var result = new List<int>();
var left = 0;
while (left < checkMap.Count - words.Length)
{
var checkWindow = checkMap[left].index + window - size;
var right = left;
var prevIndex = -size;
while (right < checkMap.Count && checkWindow >= checkMap[right].index)
{
if (checkMap[right].index >= prevIndex + size)
{
wordMap[checkMap[right].word][1] += 1;
prevIndex = checkMap[right].index;
}
right++;
}
var found = true;
foreach(var map in wordMap)
{
found &= map.Value[0] == map.Value[1];
map.Value[1] = 0;
}
if (found)
{
result.Add(checkMap[left].index);
}
left++;
}
return result;
}
}C++ solution
auto-draft, review before submit#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public vector<int> FindSubstring(string s, vector<string> words) {
var size = words[0].size();
var window = size * words.size();
var wordMap = new unordered_map<string, int[]>();
foreach (var word in words)
{
if (!wordMap.TryGetValue(word, out var map))
{
wordMap.push_back(word, map = new int[2]);
}
map[0] += 1;
}
var checkMap = new List<(int index, string word)>();
for (var i = 0; i <= s.size() - size; i++)
{
var word = s[i..(i + size)];
if (wordMap.count(word))
{
checkMap.push_back((i, word));
}
}
var result = new List<int>();
var left = 0;
while (left < checkMap.size() - words.size())
{
var checkWindow = checkMap[left].index + window - size;
var right = left;
var prevIndex = -size;
while (right < checkMap.size() && checkWindow >= checkMap[right].index)
{
if (checkMap[right].index >= prevIndex + size)
{
wordMap[checkMap[right].word][1] += 1;
prevIndex = checkMap[right].index;
}
right++;
}
var found = true;
foreach(var map in wordMap)
{
found &= map.Value[0] == map.Value[1];
map.Value[1] = 0;
}
if (found)
{
result.push_back(checkMap[left].index);
}
left++;
}
return result;
}
}Java solution
matched/originalclass Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> answer = new ArrayList<>();
HashMap<String, Integer> mapOfWords = new HashMap<>();
for (String word : words) mapOfWords.put(word, mapOfWords.getOrDefault(word, 0) + 1);
int k = words[0].length();
int n = words.length * k;
int sLen = s.length();
if (sLen < n) return answer;
int[] arr = new int[26];
for (String word : words) {
for (int i = 0; i < k; i++) {
arr[word.charAt(i) - 'a']++;
}
}
int start = 0, end = n - 1;
for (int i = 0; i <= end; i++) arr[s.charAt(i) - 'a']--;
while (end < s.length() - 1) {
if (allZeros(arr) && validWords(s.substring(start, end + 1), new HashMap<>(mapOfWords), k)) {
answer.add(start);
}
arr[s.charAt(start++) - 'a']++;
arr[s.charAt(++end) - 'a']--;
}
if (allZeros(arr) && validWords(s.substring(start, end + 1), new HashMap<>(mapOfWords), k)) {
answer.add(start);
}
return answer;
}
public boolean allZeros(int[] arr) {
return Arrays.stream(arr).allMatch(i -> i == 0);
}
public boolean validWords(String s, HashMap<String, Integer> mapOfWords, int k) {
for (int i = 0; i * k < s.length(); i++) {
String current = s.substring(i * k, (i + 1) * k);
if (!mapOfWords.containsKey(current) || mapOfWords.get(current) == 0) return false;
mapOfWords.put(current, mapOfWords.get(current) - 1);
}
return true;
}
}JavaScript solution
matched/originalvar findSubstring = function(s, words) {
let len = words[0].length; let windowSize = words.length * len;
if (s.length < windowSize) { return [];
} let m = new Map(), res = [];
// Fill Hash table with entry being (word, number of occurrences) for (let i = 0; i < words.length; i++) {
m.set(words[i], m.get(words[i]) + 1 1); }
let start = 0; while (start + windowSize - 1 < s.length) {
if (isConcat(s, new Map(m), len, start, start + windowSize-1)) { res.push(start);
} start++;
} return res;
// Let M be the length of s, N be the number of words // T.C: O(M*N)
// S.C: O(M*N), new map is used for every iteration};
const isConcat = (s, m, len, start, end) => {
let chars = m.size; for (let i = start; i <= end; i += len) {
let substr = s.substring(i, i+len); if (!m.has(substr) m.get(substr) === 0) return false;
m.set(substr, m.get(substr) - 1); if (m.get(substr) === 0) {
chars--; }
} return chars === 0;
// if we consider time complexity of substring() to be O(1), // T.C: O(N)
}Python solution
matched/originalfrom collections import defaultdict
class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:
if not s or not words:
return []
word_count = defaultdict(int)
for word in words:
word_count[word] += 1
substr_len = len(words) * len(words[0])
word_len = len(words[0])
result = []
for i in range(len(s) - substr_len + 1):
seen = defaultdict(int)
for j in range(i, i + substr_len, word_len):
word = s[j:j+word_len]
if word in word_count:
seen[word] += 1
if seen[word] > word_count[word]:
break
else:
break
else:
result.append(i)
return resultGo solution
matched/originalimport "sort"
func findSubstring(s string, words []string) []int {
sort.Strings(words)
var result []int
for i := range s {
if startsWithConcatenatedSubstring(s[i:], words) {
result = append(result, i)
}
}
return result
}
func startsWithConcatenatedSubstring(s string, words []string) bool {
var parts[] string
wl := len(words[0])
for i := range words {
startPos := wl*i
endPos := wl*(i+1)
if endPos > len(s) {
return false
}
p := s[startPos:endPos]
parts = append(parts, p)
}
sort.Strings(parts)
for i, p := range parts {
if p != words[i] {
return false
}
}
return true
}Explanation
Данный код представляет собой класс `Solution`, в котором содержится метод `FindSubstring`, предназначенный для поиска подстрок в строке `s`, которые являются конкатенацией всех слов из массива `words`. Вот пояснение к данному методу:
1. В начале метода инициализируются переменные `size` и `window`. Переменная `size` содержит длину одного слова из массива `words`, а переменная `window` - общую длину всех слов из массива `words`.
2. Создается словарь `wordMap`, где ключом является слово из массива `words`, а значением - массив из двух элементов. Первый элемент массива используется для подсчета количества вхождений данного слова в массив `words` (значение `0` увеличивается на `1` при каждом добавлении слова).
3. Затем создается список `checkMap`, который содержит кортежи с индексом и самим словом из строки `s`, если это слово содержится в `wordMap`.
4. В цикле `while` осуществляется проверка каждого слова в `checkMap` и заполняется словарь `wordMap` вторыми значениями, показывающими количество соответствующих слов в текущем окне.
5. Затем происходит проверка, все ли слова из массива `words` содержатся в текущем окне. Если все слова содержатся, их вторые значения обнуляются и индекс начала окна добавляется в результат `result`.
6. Метод возвращает список индексов начала подстрок, где все слова массива `words` содержатся в строке `s` в нужной последовательности.
Данный метод реализует алгоритм поиска подстроки, составленной из всех слов массива, в заданной строке.