[LeetCode] 859. Buddy Strings

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.

Example 4:

Input: s = "aaaaaaabc", goal = "aaaaaaacb"
Output: true

Constraints:

• 1 <= s.length, goal.length <= 2 * 104
• s and goal consist of lowercase letters.

亲密字符串。

给你两个字符串 s 和 goal ，只要我们可以通过交换 s 中的两个字母得到与 goal 相等的结果，就返回 true ；否则返回 false 。

交换字母的定义是：取两个下标 i 和 j （下标从 0 开始）且满足 i != j ，接着交换 s[i] 和 s[j] 处的字符。

例如，在 "abcd" 中交换下标 0 和下标 2 的元素可以生成 "cbad" 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/buddy-strings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路如下，首先判断几个边界条件，如果两个字符串长度不同，就是 false；如果两个字符串完全相同，但是不同字母的个数 == 字符串长度（用 hashset 记录），也是 false，因为他们是无法通过一次 swap 得到的。比如 abcdefg 这样的字符串，AB 两者都相同，但是你无论 swap 哪两个字母，最后都会导致 AB 不相同了。

一般的 case 是你需要用一个 list 收集所有相同位置上的不同字母，如果这个 list 的 size 最后不等于 2，也需要 return false，说明有超过两个位置上的字母不同，一次 swap 还不够。再判断这两个不同的字母是否能通过互相 swap 而变得相同。

时间O(n)

空间O(n)

Java实现

class Solution {
    public boolean buddyStrings(String A, String B) {
        // corner case
        if (A.length() != B.length()) {
            return false;
        }
        
        if (A.equals(B)) {
            HashSet<Character> set = new HashSet<>();
            for (char c : A.toCharArray()) {
                set.add(c);
            }
            if (set.size() < A.length()) {
                return true;
            } else {
                return false;
            }
        }
        
        // normal case
        List<Integer> diff = new ArrayList<>();
        for (int i = 0; i < A.length(); i++) {
            if (A.charAt(i) != B.charAt(i));
            diff.add(i);
        }
        
        if (diff.size() == 2) {
            if (A.charAt(diff.get(0)) == B.charAt(diff.get(1)) && A.charAt(diff.get(1)) == B.charAt(diff.get(0))) {
                return true;
            } else {
                return false;
            }
        }
    }
}

LeetCode 题目总结