亲密字符串

难度: Easy

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

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

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

示例 1：

输入：s = "ab", goal = "ba"
输出：true
解释：你可以交换 s[0] = 'a' 和 s[1] = 'b' 生成 "ba"，此时 s 和 goal 相等。

示例 2：

输入：s = "ab", goal = "ab"
输出：false
解释：你只能交换 s[0] = 'a' 和 s[1] = 'b' 生成 "ba"，此时 s 和 goal 不相等。

示例 3：

输入：s = "aa", goal = "aa"
输出：true
解释：你可以交换 s[0] = 'a' 和 s[1] = 'a' 生成 "aa"，此时 s 和 goal 相等。

提示：

1 <= s.length, goal.length <= 2 * 10⁴
s 和 goal 由小写英文字母组成

Submission

运行时间: 28 ms

内存: 16.2 MB

class Solution:
    def buddyStrings(self, s: str, goal: str) -> bool:
        if len(s) != len(goal):
            return False
        
        if s == goal:
            # Check if there is at least one repeated character in s
            return len(set(s)) < len(s)
        
        # Find the two mismatching characters in s and goal
        mismatches = [(i, s[i], goal[i]) for i in range(len(s)) if s[i] != goal[i]]
        
        if len(mismatches) != 2:
            return False
        
        # Check if swapping the two mismatching characters in s results in goal
        first_mismatch, second_mismatch = mismatches
        return (
            first_mismatch[1] == second_mismatch[2] and
            first_mismatch[2] == second_mismatch[1]
        )

solution = Solution()
print(solution.buddyStrings("ab", "ba"))  # True
print(solution.buddyStrings("ab", "ab"))  # False
print(solution.buddyStrings("aa", "aa"))  # True

Explain

该题解首先检查两个字符串 s 和 goal 是否具有相同的长度，如果不相同则直接返回 False。接着，如果 s 和 goal 完全相同，那么检查 s 中是否至少有一个字符出现了不止一次；如果有，通过交换同一个字符来保持字符串不变即可满足题目条件。如果 s 和 goal 不完全相同，则寻找两者之间不匹配的字符位置。如果恰好有两处不匹配，检查这两处字符是否可以通过一次交换使 s 变为 goal。具体来说，就是 s 中第一个不匹配字符应与 goal 中第二个不匹配字符相同，反之亦然。

时间复杂度: O(n)

空间复杂度: O(k)

class Solution:
    def buddyStrings(self, s: str, goal: str) -> bool:
        if len(s) != len(goal):
            return False  # 字符串长度不同，无法通过交换变为相同
        
        if s == goal:
            # 检查是否有重复字符，使得可以交换这两个相同的字符
            return len(set(s)) < len(s)
        
        # 寻找两个字符串中不匹配的字符
        mismatches = [(i, s[i], goal[i]) for i in range(len(s)) if s[i] != goal[i]]
        
        if len(mismatches) != 2:
            return False  # 不匹配的位置不是两处，不能通过一次交换解决
        
        # 检查两处不匹配的字符是否可以通过交换使 s 变为 goal
        first_mismatch, second_mismatch = mismatches
        return (
            first_mismatch[1] == second_mismatch[2] and
            first_mismatch[2] == second_mismatch[1]
        )

Explore

当s和goal完全相同时，题目要求通过交换两个字符使得s等于goal。如果s中所有字符都是唯一的，那么交换任何两个字符都会改变s的内容，导致s不再与goal相同。因此，只有当s中至少有一个字符出现两次或更多时，我们才能通过交换这两个相同的字符，使得s在视觉上看起来仍然保持不变，满足题目的要求。如果没有重复字符，即使s和goal完全相同，也无法通过这样的交换达到题目要求的效果，因此算法返回False。

如果s与goal之间的不匹配位置超过两处或少于两处，无法仅通过一次交换使两个字符串相等。如果只有一处不匹配，无法找到另一处进行有效的交换。如果有三处或更多不匹配，一次交换（即交换两个字符的位置）无法同时纠正所有不匹配的位置。因此，只有当恰好有两处字符不匹配时，我们可以尝试交换s中这两处不匹配的字符，检查交换后s是否能变为goal。如果交换后两处字符都能匹配上对方原位置的字符，则说明一次交换可以解决问题，否则不行。

这种方法在大多数情况下是有效的，因为它直接检查了通过一次交换能否解决两处不匹配的问题。具体来说，如果s中的第一个不匹配字符可以与goal中的第二个不匹配字符交换，并且s中的第二个不匹配字符也可以与goal中的第一个不匹配字符交换，那么一次交换就能使s变为goal。这种检查是基于题目设定的，即只能进行一次交换。不存在特殊情况会导致这种检查方法出错，只要保证不匹配的位置恰好有两处，并且这两处可以互换，就可以确保算法的正确性。