271. Encode and Decode strings

Vui lòng đọc hiểu đề trước khi đọc bài viết này tại đây: (Vì bài này phải có leetcode premium mới xem được, nên mình sẽ dùng tạm link clone problem của trang neetcode.io, thank you so much 👏)

https://neetcode.io/problems/string-encode-and-decode

Table of Contents

1. Cách tiếp cận vấn đề

Yêu cầu bài toán thật đơn giản, ta cần implement 2 hàm encode và decode, với mục đích là encode list các phần tử String thành một String duy nhất và decode ngược lại từ String sang list của các phần tử String.

Hay nói cách khác, từ 1 list input string ban đầu, khi đi qua 2 hàm encode và decode, ta cần trả nó đúng về dạng ban đầu là list input string mà vẫn giữ nguyên các giá trị.

Ví dụ: ["neet", "code", "love", "you"]

• Khi đi qua hàm encode sẽ trả về 1 String nào đó do ta tự quy ước, ví dụ: "neetcodeloveyou"
• Khi đi qua hàm decode sẽ cần trả về lại list input string ban đầu: ["neet", "code", "love", "you"]

Tuy có vẻ đơn giản nhưng việc biến đổi từ list string sang 1 string ở hàm encode đã làm thay đổi cấu trúc lưu trữ của dữ liệu. Ta cần phải có một quy ước nào đó để khi hoàn thành bước encode đó rồi, ta có thể dễ dàng dựa vào đó để decode ngược lại thành list string ban đầu.

Nó giống như việc ở thời chiến tranh, các bức thư được mã hóa theo một quy tắc nhất định, và chỉ những người liên quan mới nắm được bộ key để có thể giải mã nó. Với bài toán của chúng ta thì đơn giản hơn nhiều, ta thử suy nghĩ một số idea từ sơ khai nhất và kiểm tra xem chúng có khả thi để implement hay không.

Đầu tiên chúng ta có thể suy nghĩ đến việc encode bằng cách thêm một ký tự đặc biệt nào đó để chen giữa các từ, ví dụ với ký tự '/': "neet/code/love/you" sau đó khi decode chỉ cần split string theo ký tự '/' đó là được. Tuy nhiên đời không như là mơ, ta cần nhìn lại yêu cầu đề bài khi string có thể chứa các ký tự UTF-8, hay nói cách khác là chuỗi string hoàn toàn có thể chứa '/' (ví dụ "neet/", "code/",.. hay tệ hơn là "///", "//",...) và ta không thể dùng nó để phân biệt giữa các từ. Ta cũng không thể tìm bất kỳ ký tự đặc biệt nào khác có thể làm điều đó, vì bất kỳ ký tự nào mà chúng ta có thể gõ ra từ bàn phím đều thuộc bộ UTF-8 này.

Chèn giữa để split không được, thì ta chèn đầu😁 ta sẽ encode bằng cách dùng một con số đứng đầu mỗi từ đại diện cho chính chiều dài của chuỗi đó, ví dụ: "4neet4code4love3you" . Sau đó ở bước decode mỗi khi ta gặp một con số nào đó thì ta chỉ cần đọc đúng số lượng ký tự sao cho bằng với số đó là được, ví dụ: gặp 4 thì ta đọc được chữ "neet" sau đó gặp 4 tiếp thì ta đọc được chữ "code" và tiếp tục cho đến hết chuỗi. Tuy nhiên chuỗi ban đầu hoàn toàn có thể chứa một con số khác ở đầu chuỗi, ví dụ "123neet" có 7 ký tự khi encode sẽ thành "7123neet" và khi decode chúng ta không thể phân biệt được con số nào mới là đại diện chiều dài của chuỗi 7, 71, 712 hay 7123???

Sau khi hiểu được một số cách làm sơ khai nhất mà chắc chắn rất nhiều bạn khi tiếp cận bài toán đều có thể suy nghĩ tương tự như vậy, thì solution của chúng ta chỉ đơn giản là kết hợp chúng lại để tạo ra được một cách làm hoàn hảo nhất. Chính vì vậy khi giải một bài toán nào đó, dù là khó hay dễ thì ta vẫn nên tiếp cận nó từ những cách làm sơ khai nhất để hiểu rõ được bản chất của vấn đề, để rồi từ đó có thể hoàn thiện dần và tạo ra được một phiên bản cuối cùng hoàn thiện nhất. Trừ khi bạn đã luyện tập thật nhiều bài ở nhiều dạng một cách thuần thục nhất thì khi nhìn vào một bài toán may ra mới có thể nghĩ ra được solutions tốt nhất ngay từ lần đầu tiên, tuy nhiên cũng phải cẩn thận vì chính sự chủ quan và thân thuộc đó đôi khi lại giết chết chúng ta, vì sẽ có những bài toán na ná nhau nhưng chỉ khác một vài chi tiết nhỏ quan trọng và nếu không đọc và phân tích đủ sâu sẽ dễ bẫy bạn đi vào những suy nghĩ lối mòn, những cái gọi là thân thuộc đó và từ đó đưa ra những solution không chính xác.

2. Solution & Phân Tích

Khi encode, ta vẫn sẽ dùng một số đứng đầu mỗi chuỗi để đại diện cho chiều dài của chuỗi đó, nhưng ở giữa số và chuỗi đó, ta sẽ thêm vào một ký tự quy ước nào đó bất kỳ (miễn không phải là số), ví dụ với ký tự '/':

chiều dài chuỗi 1/chuỗi 1chiều dài chuỗi 2/chuỗi 2 ...

Và khi decode, ta chỉ cần:

• Đọc chiều dài từng chuỗi bằng việc đọc các con số cho đến khi gặp ký tự '/' thì dừng lại
• Đọc các ký tự của chuỗi ở sau '/' bằng đúng chiều dài đã đọc được, sau đó thêm chuỗi đã đọc được vào mảng kết quả.
• Cứ làm như vậy cho đến khi ta duyệt đến vị trí cuối cùng của chuỗi cuối cùng thì dừng lại.

Cách làm này đã giải quyết được 2 vấn đề lớn khi chúng ta decode:

1. Tách biệt được giữa chiều dài từng chuỗi với chính chuỗi đó thông qua ký tự '/', nhờ vậy ta sẽ không lo ở đầu chuỗi có một con số nào đó lẫn vào con số xác định chiều dài chuỗi nữa, ví dụ: "5/12345" ta có thể hiểu là chuỗi "12345" có 5 ký tự.
2. Ta cũng không cần lo liệu ký tự ta dùng để tách biệt số và chuỗi (trong trường hợp này là '/') có xuất hiện ở chuỗi hay không, vì ta chỉ dùng đúng 1 ký tự mà thôi, và ký tự đó sẽ theo sau con số xác định chiều dài, nên nếu có thêm 1 ký tự nữa liền kề sau nó thì cũng sẽ không làm ảnh hưởng gì đến logic decode của chúng ta, ví dụ: "6///abcd" ta có thể hiểu là chuỗi "//abcd" có 6 ký tự.

Quay trở lại với ví dụ ban đầu: ["neet", "code", "love", "you"]

Process khi encode:

Process khi decode:

Space-Complexity: O(n) cho cả 2 hàm encode và decode

Time-Complexity: O(n) cho cả 2 hàm encode và decode

n: chiều dài của tất cả các chuỗi kết hợp lại.

3. Code

Mình sẽ sử dụng Java để minh họa cho solution trên, điểm khác biệt duy nhất là sử dụng thêm con trỏ j để kết hợp với con trỏ i tạo thành các khoảng đại diện cho size và word, từ đó sử dụng method substring để lấy ra giá trị thay vì duyệt qua từng ký tự, tuy nhiên về cơ bản thì idea vẫn là như nhau.

• Từ i tới j (vị trí của '/') sẽ là chiều dài của size, từ đó ta chuyển nó thành số nguyên.
• Gán i = j + 1 + size (vị trí cuối cùng của chuỗi word đang xét), từ j + 1 (vị trí sau '/') tới i lúc này chính là chiều dài của chuỗi word đang xét, lúc này ta chỉ cần lấy word trong khoảng đó bằng method: substring(startIndex, endIndex)