Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Table Of Contents
Xin chào các bạn yêu quý của Learning AI With Losers! Mình là Loser1 đây!
Sau một ngày lười biếng bỏ lỡ Day 26 😅, hôm nay chúng ta quay trở lại với bài Easy thứ 5 trong series về swap chuỗi! Let’s find our string soulmates! 🎭
1790. Check if One String Swap Can Make Strings Equal
EasyBạn được cung cấp hai chuỗi s1 và s2 có độ dài bằng nhau. Một phép hoán đổi chuỗi là thao tác chọn hai chỉ số trong một chuỗi (không nhất thiết phải khác nhau) và hoán đổi các ký tự tại các chỉ số đó.
Trả về true nếu có thể làm cho cả hai chuỗi bằng nhau bằng cách thực hiện tối đa một phép hoán đổi chuỗi trên chính xác một trong hai chuỗi. Nếu không, trả về false.
Ví dụ:
Example 1:
Input: s1 = "bank", s2 = "kanb" Output: true Explanation: Ví dụ, hoán đổi ký tự đầu tiên với ký tự cuối cùng của s2 để tạo thành "bank".
Example 2:
Input: s1 = "attack", s2 = "defend" Output: false Explanation: Không thể làm cho chúng bằng nhau với một phép hoán đổi chuỗi.
Example 3:
Input: s1 = "kelb", s2 = "kelb" Output: true Explanation: Hai chuỗi đã bằng nhau, do đó không cần thực hiện phép hoán đổi chuỗi nào.
Ràng buộc:
1 <= s1.length, s2.length <= 100s1.length == s2.lengths1vàs2chỉ bao gồm các chữ cái tiếng Anh viết thường.
🎭 Problem Visualization
Hãy tưởng tượng bạn đang chơi trò ghép đôi chữ cái:
s1: "b a n k"
s2: "k a n b"
⬇️ ⬇️
Swap hai chữ này!
Hoặc:
s1: "k e l b"
s2: "k e l b"
✨ Perfect match!
🔥 First Thoughts & Intuition
Giống như trò chơi tìm cặp đôi hoàn hảo:
Perfect Match:
k e l b
k e l b
✅ Không cần swap!
One Swap Needed:
b a n k
k a n b
🔄 Chỉ cần 1 lần swap!
Mission Impossible:
a t t a c k
d e f e n d
❌ Không thể match!
💡 Approach
1. Character Matching Game 🎲
Kiểm tra từng cặp ký tự:
Match Counter:
b ≠ k (Diff #1)
a = a (Match!)
n = n (Match!)
k ≠ b (Diff #2)
2. Swap Analysis 🔄
Điều kiện hợp lệ:
- Đúng 0 điểm khác biệt (perfect match)
- Đúng 2 điểm khác biệt (có thể swap)
- Các ký tự khác phải ghép cặp được
🚀 Implementation
C++
class Solution {
public:
bool areAlmostEqual(string s1, string s2) {
if (s1.length() != s2.length()) return false;
int diff_count = 0;
char s1_first = '\0', s1_second = '\0';
char s2_first = '\0', s2_second = '\0';
for (int i = 0; i < s1.length(); i++) {
if (s1[i] != s2[i]) {
diff_count++;
if (diff_count == 1) {
s1_first = s1[i];
s2_first = s2[i];
} else if (diff_count == 2) {
s1_second = s1[i];
s2_second = s2[i];
} else return false;
}
}
return (diff_count == 0) ||
(diff_count == 2 && s1_first == s2_second && s1_second == s2_first);
}
};🎯 Example Walkthrough
Ví Dụ 1: Cần Đổi Một Lần
Input: s1: "bank" s2: "kanb"
Phân tích từng bước:
- b ≠ k ⚡️ Khác #1
- a = a ✨ Giống!
- n = n ✨ Giống!
- k ≠ b ⚡️ Khác #2
Kết quả: true (đổi b↔k là xong!)
Ví Dụ 2: Không Thể Đổi
Input: s1: "attack" s2: "defend"
Phân tích:
- a ≠ d ⚡️
- t ≠ e ⚡️
- t ≠ f ⚡️ Quá nhiều khác biệt! ❌
Ví Dụ 3: Đã Giống Nhau
Input: s1: "kelb" s2: "kelb"
Phân tích:
- k = k ✨
- e = e ✨
- l = l ✨
- b = b ✨ Hoàn hảo! Không cần đổi! ✅
📊 Đánh Giá Độ Phức Tạp
Thời Gian: O(N)
Chỉ cần duyệt qua chuỗi một lần: k → e → l → b ⏱️ Tăng tuyến tính theo độ dài chuỗi
Bộ Nhớ: O(1)
Chỉ dùng: 🧮 Vài biến đơn giản:
- đếm số khác biệt
- bốn biến ký tự
- biến đếm vòng lặp
💎 Những Điểm Cần Nhớ
- 🎯 Ba Trường Hợp Có Thể:
- Giống hệt nhau (0 khác biệt)
- Đổi được (2 khác biệt)
- Không thể đổi (các trường hợp còn lại)
- 🎨 Kỹ Thuật Xử Lý:
- Kiểm tra từng cặp ký tự
- Lưu lại vị trí khác biệt
- Xác nhận khả năng đổi chỗ
Sau một ngày nghỉ ngơi, hi vọng bài viết này giúp các bạn "khởi động" lại! Đôi khi lười biếng cũng cần thiết, miễn là biết quay lại đúng lúc! 😊
Follow mình tại Learning AI with Loser để cập nhật các bài giải Leetcode hàng ngày nhé! 💻✨
CODE EDITOR
#leetcode #leetcodedaily #algorithms #programming #learningwithlosers #stringmanipulation #codinglife
