30. Substring with Concatenation of All Words

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

Tất cả các từ trong words đều có độ dài bằng nhau

Độ dài chuỗi con cần xét là total_len = word_len * word_count

Duyệt qua từng vị trí bắt đầu hợp lệ trong 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)

Tạo một hashmap (object) lưu số lần xuất hiện của từng từ trong words

Duyệt qua 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ừ)

Với mỗi window, kiểm tra xem các từ tách ra có khớp tần suất với hashmap không

Nếu khớp, thêm chỉ số bắt đầu vào kết quả

Solution

typescripttypescript

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};

💡

Giải thích ngắn gọn

Dùng sliding window để kiểm tra từng window có độ dài hợp lệ

Hashmap giúp so sánh nhanh tần suất từ

Duyệt theo từng offset để bao phủ mọi trường hợp

Loading content...

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};