271. Encode and Decode Strings
Tags:
Medium
Skills:
String
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Để giải bài toán này, bạn cần thiết kế một phương pháp encode một mảng các chuỗi thành một chuỗi duy nhất, và một phương pháp decode chuỗi đó về lại mảng ban đầu
Hai ý tưởng phổ biến nhất là:
- Length-prefix encoding
- Với mỗi chuỗi, bạn ghi độ dài chuỗi, một ký tự phân tách (VD
#), rồi đến nội dung chuỗi. Khi giải mã, bạn chỉ cần đọc số trước dấu#để biết cần lấy bao nhiêu ký tự tiếp theo làm chuỗi gốc - Fixed-width length prefix
- Với mỗi chuỗi, bạn ghi độ dài của chuỗi bằng một số ký tự cố định (Vd 4 ký tự) sau đó, là nội dung chuỗi. Khi giải mã, bạn cứ đọc 4 ký tự để lấy độ dài, rồi lấy tiếp số ký tự tương ứng
Approach - Length-prefix encoding
Solution
typescripttypescript
1/**
2 * Encodes a list of strings to a single string.
3 */
4function encode(strs: string[]): string {
5 return strs.map(str => `${str.length}#${str}`).join('');
6};
7
8/**
9 * Decodes a single string to a list of strings.
10 */
11function decode(s: string): string[] {
12 const res: string[] = []
13 let i = 0
14 while (i < s.length) {
15 let j = i;
16 while (s[j] !== '#' && j < s.length) j++
17 const len = parseInt(s.slice(i, j), 10);
18 res.push(s.slice(j + 1, j + 1 + len));
19 i = j + 1 + len
20 }
21
22 return res;
23};
24
25/**
26 * Your functions will be called as such:
27 * decode(encode(strs));
28 */💡
Tóm tắt
- Ý tưởng: Mã hóa mỗi chuỗi thành
<dộ dài>#<chuỗi>, ghép lại thành một chuỗi duy nhất - Khi giải mã: Đọc số trước dấu
#để biết cần lấy bao nhiêu ký tự tiếp theo - TC: O(n) với n là tổng độ dài các chuỗi