859. Buddy Strings

📋 Đề Bài

Given two strings s and goal, return true if you can swap two letters in s so the result is equal to goal, otherwise, return false.

Swapping letters is defined as taking two indices i and j (0-indexed) such that i != j and swapping the characters at s[i] and s[j].

For example, swapping at indices 0 and 2 in "abcd" results in "cbad".

Example 1:

Input: s = "ab", goal = "ba"
Output: true
Explanation: You can swap s[0] = 'a' and s[1] = 'b' to get "ba", which is equal to goal.

Example 2:

Input: s = "ab", goal = "ab"
Output: false
Explanation: The only letters you can swap are s[0] = 'a' and s[1] = 'b', which results in "ba" != goal.

Example 3:

Input: s = "aa", goal = "aa"
Output: true
Explanation: You can swap s[0] = 'a' and s[1] = 'a' to get "aa", which is equal to goal.

Constraints:

1 <= s.length, goal.length <= 2 * 10⁴
s and goal consist of lowercase letters.

🧠 Thuật Toán & Kỹ Thuật

Hash Table (Bảng băm)String (Chuỗi)

⏱️ Thời gian O(n)

💾 Không gian O(n)

💻 Lời Giải

C++ 0859-buddy-strings.cpp

class Solution {
public:
    bool buddyStrings(string s, string goal) {
        int n = s.size();
        int m = goal.size();
        
        if (n != m) {
            return false;
        }
        
        int diff1 = -1, diff2 = -1;
        unordered_set<char> us;
        
        for (int i = 0; i < n; ++i) {
            if (s[i] != goal[i]) {
                if (diff1 == -1) {
                    diff1 = i;
                }
                else if (diff2 == -1) {
                    diff2 = i;
                }
                else {
                    return false;
                }
            }
            us.insert(s[i]);
        }
        
        if (diff1 != -1 and diff2 != -1) {
            return s[diff1] == goal[diff2] and s[diff2] == goal[diff1];
        }
        
        if (diff1 != -1) {
            return false;
        }
        
        return (int)(us.size()) < n;
    }
};