269. Alien Dictionary
Tags:
Hard
Skills:
Graph
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 xác định thứ tự của các ký tự trong một ngôn ngữ ngoài hành tinh dựa trên danh sách các từ được sắp xếp theo thứ tự từ điển của ngôn ngữ đó
Sorted lexicographically (sắp xếp theo thứ tự từ điển) là cách sắp xếp các phần tử (chuỗi ký tự, từ, hoặc số) dựa trên thứ tự của chúng trong từ điển. Điều này có nghĩa là các phần tử được so sánh từ trái sang phải, từng ký tự một, theo thứ tự bảng chữ cái hoặc mã ký tự (như ASCII hoặc Unicode).
Đặc điểm của thứ tự từ điển
Ví dụ minh họa
["apple", "banana", "app"], sau khi sắp xếp lexicographically sẽ là: ["app", "apple", "banana"].["2", "10", "3"], thứ tự lexicographically sẽ là: ["10", "2", "3"] (so sánh từng ký tự, không phải giá trị số).Phân tích
Approach
Solution
1function alienOrder(words: string[]): string {
2 const adj_list: Map<string, Set<string>> = new Map();
3 const in_degree: Map<string, number> = new Map();
4
5 // 1. Init grapj and in_degree
6 for (const word of words) {
7 for (const char of word) {
8 if (!adj_list.has(char)) adj_list.set(char, new Set());
9 if (!in_degree.has(char)) in_degree.set(char, 0)
10 }
11 }
12
13 // 2. Build graph and in_degree
14 for (let i = 1; i < words.length; i++) {
15 const w1 = words[i - 1];
16 const w2 = words[i];
17 const min_len = Math.min(w1.length, w2.length);
18 let found_diff = false;
19
20 for (let j = 0; j < min_len; j++) {
21 const c1 = w1[j];
22 const c2 = w2[j];
23
24 if (c1 !== c2) {
25 if (!adj_list.get(c1)!.has(c2)) {
26 adj_list.get(c1)!.add(c2);
27 in_degree.set(c2, in_degree.get(c2)! + 1);
28 }
29 found_diff = true;
30 break;
31 }
32 }
33
34 if (!found_diff && w1.length > w2.length) return ""
35 }
36
37 // 3. Topo
38 const queue: string[] = [];
39 for (const [char, degree] of in_degree) {
40 if (degree === 0) queue.push(char);
41 }
42
43 const res: string[] = [];
44 while (queue.length > 0) {
45 const char = queue.shift()!;
46 res.push(char);
47 for (const neighbor of adj_list.get(char)!) {
48 in_degree.set(neighbor, in_degree.get(neighbor)! - 1)
49 if (in_degree.get(neighbor) === 0) queue.push(neighbor);
50 }
51 }
52
53 if (res.length !== in_degree.size) return ""
54
55 return res.join("")
56};