30. Substring with Concatenation of All Words
Tags:
Hard
Skills:
Sliding Window
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu tìm tất cả các chỉ số bắt đầu của các chuỗi con trong chuỗi s là sự nối tiếp của tất cả các từ trong mảng words (mỗi từ xuất hiện đúng số lần như trong words , thứ tự bất kỳ)
Phân tích
words đều có độ dài bằng nhautotal_len = word_len * word_count s , tách chuỗi con thành các đoạn nhỏ bằng độ dài từ, kiểm tra tần suất xuất hiện của từng từ so với words Approach (sliding window +hashmap)
words s với các window, mỗi lần dịch 1 ký tự (hoặc tối ưu hơn là dịch theo từng ký tự đầu của từ)Solution
1function findSubstring(s: string, words: string[]): number[] {
2 if (s.length === 0 || words.length === 0) return [];
3 const word_len = words[0].length;
4 const word_count = words.length;
5 const total_len = word_len * word_count;
6 let word_map: Record<string, number> = {};
7
8 for (const word of words) {
9 word_map[word] = (word_map[word] || 0) + 1;
10 }
11
12 const res: number[] = [];
13 for (let i = 0; i < word_len; i++) {
14 let left = i, right = i, count = 0;
15 let window_map: Record<string, number> = {};
16
17 while (right + word_len <= s.length) {
18 const word = s.substring(right, right + word_len);
19 right += word_len;
20
21 if (word_map[word] !== undefined) {
22 window_map[word] = (window_map[word] || 0) + 1;
23 count++
24
25 while (window_map[word] > word_map[word]) {
26 const left_word = s.substring(left, left + word_len);
27 window_map[left_word]--;
28 count--
29 left += word_len
30 }
31
32 if (count === word_count) {
33 res.push(left)
34 }
35 } else {
36 window_map = {};
37 count = 0;
38 left = right
39 }
40 }
41 }
42
43 return res
44};