30 ngày chống COVID cùng Leetcode | Ngày 09
Bài toán này dù đơn giản thôi, nhưng làm tôi tốn buổi chiều.
Hai xâu S và T bao gồm các chữ cái và dấu # biểu chưng cho phím backspace trong mọi trình soạn thảo văn bản. Kiểm tra xem hai xâu S và T có bằng nhau hay không.
Tạo hai mảng Stack ứng với hai xâu, duyệt trên từng xâu, nếu S[i] = # thì pop khỏi Stack, chính là phần tử phía trước, ngược lại push vào Stack. Cuối cùng, so sánh 2 stack nếu bằng nhau sẽ là kết quả, đây chính là cách hoạt động của trình soạn thảo văn bản mà ta dùng hằng ngày.
Giải pháp này khá hay nhưng vì nó quá phổ thông và tốn dung lượng nên chưa làm mọi người thỏa mãn. Giải pháp tiếp theo dùng Two Pointer, tôi nghĩ Two Pointer là một cách nghĩ cần phải có sự khéo léo. À quên, giải pháp trên sẽ mất độ phức tạp O(M+N) và độ phức tạp không gian O(M+N) nhé.
Cách hoạt động của trình soạn thảo văn bàn là thụ động, bởi vì nó không biết ta viết SAI chỗ nào để mà dùng backspace sau đó. Còn với bài toán này, đúng là phí, bởi ta đã biết được cái xâu kia sẽ phải nhấn bao nhiêu lần backspace. Ta sẽ không tư duy như trình soạn thảo văn bản là chạy tử đầu đến cuối, ta sẽ chạy ngược lại, từ cuối về đầu, bởi ta hoàn toàn có thể làm chủ số backspace mà người dùng đã bấm ngay từ đầu. Mấu chốt vấn đề nằm ở đây.
Được rồi, duyệt từ cuối chuỗi, nếu 1 ký tự là backspace (#), ký tự tiếp theo sẽ bị bỏ qua. Nếu nó không bị bỏ qua, nó chính là một phần của kết quả cuối cùng.
Có thể hiểu hai vòng while mỗi lần chạy ta sẽ tìm xâu rút gọn tiếp theo sau khi xóa, ta so sánh hai ký tự cuối tại thời điểm đó, nếu nó không bằng nhau thì tức là hai xâu này không cùng một mối rồi. Dòng thứ 43 hãy hiểu đơn giản là ta không thể so sánh 1 xâu null với 1 xâu còn ký tự.
Hết rồi, hẹn gặp Leetcode vào ngày mai. Cảm ơn bạn !
Input: S = "ab#c", T = "ad#c" Output: true Explanation: Both S and T become "ac".Tương tự như khi ta gõ phím, kết quả sẽ là "ac".
Input: S = "ab#c", T = "ad#c" Output: true Explanation: Both S and T become "ac".
Input: S = "a##c", T = "#a#c" Output: true Explanation: Both S and T become "c".
Input: S = "a#c", T = "b" Output: false Explanation: S becomes "c" while T becomes "b".Đề bài đơn giản thế này chắc không phải giải thích gì nhiều. Giải pháp đầu tiên ta sẽ nghĩ tới trong đầu sẽ là dùng Stack, chắc chắn rồi, ngửi thấy mùi Stack trong đây.
Tạo hai mảng Stack ứng với hai xâu, duyệt trên từng xâu, nếu S[i] = # thì pop khỏi Stack, chính là phần tử phía trước, ngược lại push vào Stack. Cuối cùng, so sánh 2 stack nếu bằng nhau sẽ là kết quả, đây chính là cách hoạt động của trình soạn thảo văn bản mà ta dùng hằng ngày.
Giải pháp này khá hay nhưng vì nó quá phổ thông và tốn dung lượng nên chưa làm mọi người thỏa mãn. Giải pháp tiếp theo dùng Two Pointer, tôi nghĩ Two Pointer là một cách nghĩ cần phải có sự khéo léo. À quên, giải pháp trên sẽ mất độ phức tạp O(M+N) và độ phức tạp không gian O(M+N) nhé.
Cách hoạt động của trình soạn thảo văn bàn là thụ động, bởi vì nó không biết ta viết SAI chỗ nào để mà dùng backspace sau đó. Còn với bài toán này, đúng là phí, bởi ta đã biết được cái xâu kia sẽ phải nhấn bao nhiêu lần backspace. Ta sẽ không tư duy như trình soạn thảo văn bản là chạy tử đầu đến cuối, ta sẽ chạy ngược lại, từ cuối về đầu, bởi ta hoàn toàn có thể làm chủ số backspace mà người dùng đã bấm ngay từ đầu. Mấu chốt vấn đề nằm ở đây.
Được rồi, duyệt từ cuối chuỗi, nếu 1 ký tự là backspace (#), ký tự tiếp theo sẽ bị bỏ qua. Nếu nó không bị bỏ qua, nó chính là một phần của kết quả cuối cùng.
Có thể hiểu hai vòng while mỗi lần chạy ta sẽ tìm xâu rút gọn tiếp theo sau khi xóa, ta so sánh hai ký tự cuối tại thời điểm đó, nếu nó không bằng nhau thì tức là hai xâu này không cùng một mối rồi. Dòng thứ 43 hãy hiểu đơn giản là ta không thể so sánh 1 xâu null với 1 xâu còn ký tự.
Hết rồi, hẹn gặp Leetcode vào ngày mai. Cảm ơn bạn !
Nhận xét
Đăng nhận xét