Hey hey, it’s your boy Loser1 from Learning AI with Losers, back with another chill Leetcode Daily Challenge! 🌟 Hôm nay, chúng ta sẽ cùng nhau khám phá một bài toán thú vị liên quan đến chuỗi: Clear Digits. Chuẩn bị một tách cà phê ☕ và cùng mình bước vào hành trình giải quyết bài toán này nhé!

Input: s = "abc"
Output: "abc"
Giải thích:
Không có chữ số nào trong chuỗi.
    

Input: s = "cb34"
Output: ""
Giải thích:
Đầu tiên áp dụng thao tác trên s[2], chuỗi trở thành "c4".
Sau đó áp dụng thao tác trên s[1], chuỗi trở thành "".
    

💡 Intuition (Cảm hứng ban đầu)

Bạn có một chuỗi s gồm các chữ cái thường ('a' → 'z') và các chữ số ('0' → '9'). Mỗi khi gặp một chữ số trong chuỗi, bạn cần thực hiện hai việc:

1. Xóa chính chữ số đó.
2. Xóa ký tự không phải số gần nhất bên trái của nó.

Ví dụ:

• "cb34" → c4 (xóa 3 và b) → "" (xóa 4 và c).

Thoạt nhìn, bài toán có vẻ phức tạp vì yêu cầu xóa cả ký tự trước đó, nhưng nếu bạn suy nghĩ kỹ, nó thực chất là một bài toán xử lý chuỗi theo thứ tự từ trái sang phải. Điều này gợi ý ngay lập tức về việc sử dụng Stack (ngăn xếp) – một cấu trúc dữ liệu tuyệt vời để xử lý các vấn đề liên quan đến "lưu trữ tạm thời" và "thao tác ngược". 🔥

🔑 Approach (Phương pháp tiếp cận)

🌟 Ý tưởng chính:

Chúng ta sẽ sử dụng Stack để lưu trữ các ký tự chữ cái và xử lý từng ký tự trong chuỗi theo cách sau:

1. Nếu ký tự hiện tại là chữ cái, thêm nó vào stack.
2. Nếu ký tự hiện tại là chữ số, thực hiện thao tác xóa:

• Pop (lấy ra) phần tử trên cùng của stack (nếu stack không rỗng).

1. Sau khi duyệt hết chuỗi, các ký tự còn lại trong stack chính là kết quả cuối cùng.

🛠 Triển khai chi tiết:

1. Duyệt qua chuỗi ký tự một lần duy nhất.
2. Sử dụng stack để lưu trữ các chữ cái.
3. Khi gặp chữ số, pop một phần tử khỏi stack (nếu có).
4. Cuối cùng, nối các phần tử còn lại trong stack để tạo thành chuỗi kết quả.

⏳ Quá trình xóa diễn ra từ trái sang phải, đúng như yêu cầu của bài toán!

🔢 Complexity Analysis (Phân tích độ phức tạp)

Time Complexity (Độ phức tạp thời gian):

• O(n): Chúng ta duyệt qua chuỗi một lần duy nhất, và mỗi phần tử chỉ được đẩy vào hoặc lấy ra khỏi stack một lần.

Space Complexity (Độ phức tạp không gian):

• O(n): Stack có thể chứa tối đa n ký tự nếu không có chữ số nào trong chuỗi.

💻 Code Implementation (Triển khai mã nguồn)

class Solution {
public:
    string clearDigits(string s) {
        stack<char> mystk; // Khởi tạo stack để lưu chữ cái

        // Duyệt qua từng ký tự trong chuỗi
        for (char c : s) {
            if (isdigit(c)) { 
                // Nếu là chữ số, xóa ký tự trước đó (nếu có)
                if (!mystk.empty()) {
                    mystk.pop();
                }
            } else {
                // Nếu là chữ cái, thêm vào stack
                mystk.push(c);
            }
        }

        // Tạo chuỗi kết quả từ các ký tự còn lại trong stack
        string ans = "";
        while (!mystk.empty()) {
            ans += mystk.top(); // Lấy phần tử trên cùng của stack
            mystk.pop();
        }

        // Đảo ngược chuỗi vì stack lấy từ cuối về đầu
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

🎨 Visualization (Minh họa chi tiết)

Hãy cùng xem thuật toán hoạt động như thế nào với ví dụ s = "cb34" nhé! 🔍

📌 Cuối cùng, stack rỗng ⇒ Kết quả trả về là chuỗi rỗng "". Chính xác như mong đợi! ✅

🎯 Final Thoughts (Nhận xét cuối cùng)

🔥 Một bài toán khá đơn giản nhưng lại giúp ta ôn tập cách sử dụng Stack để xử lý chuỗi. Đây là những điểm quan trọng mình rút ra từ bài này:
✅ Stack rất hữu ích khi cần xử lý các phần tử theo thứ tự từ trái qua phải, đặc biệt là khi có yêu cầu "xoá phần tử trước đó".
✅ Cẩn thận với điều kiện stack không rỗng trước khi gọi pop() để tránh lỗi!
✅ Ứng dụng trong thực tế: Kỹ thuật này rất giống với cách trình duyệt hoạt động khi bạn bấm nút "Back" để quay lại trang trước đó.

📚 Bonus Tips (Mẹo bổ sung)

1. Tối ưu hóa bộ nhớ: Nếu bạn không muốn sử dụng stack, bạn cũng có thể dùng một chuỗi tạm để lưu trữ các ký tự chữ cái. Cách này giúp giảm bớt việc sử dụng cấu trúc dữ liệu phức tạp.
2. Kiểm tra input đặc biệt: Hãy đảm bảo rằng code của bạn xử lý đúng các trường hợp đặc biệt, chẳng hạn như chuỗi toàn chữ số ("12345") hoặc chuỗi rỗng ("").

🎉 Kết luận

Vậy là chúng ta đã hoàn thành bài Day 32 - Clear Digits! 🎉 Hy vọng bạn đã hiểu rõ cách sử dụng Stack để giải quyết bài toán này. Nếu bạn thấy bài viết hữu ích, đừng quên để lại comment và chia sẻ với bạn bè nhé! 🚀🔥

Hẹn gặp lại ở Day 33 với một thử thách thú vị khác từ Leetcode Daily Challenge! 💡
👉 Bạn có thích bài toán này không? Hãy để lại ý kiến của bạn dưới phần bình luận nhé! 💬👇

CODE EDITOR

📌 Hashtags:
#leetcode #leetcodedaily #coding #datastructures #algorithms #learningwithlosers