leetcode
leetcode 751 ~ 800
亲密字符串

亲密字符串

难度:

标签:

题目描述

代码结果

运行时间: 28 ms, 内存: 16.2 MB


/*
 题目思路:
 使用 Java Stream API 来处理字符串。
 1. 如果 s 和 goal 的长度不相同,直接返回 false。
 2. 如果 s 和 goal 相同,检查 s 中是否有重复的字符,如果有,返回 true。
 3. 如果 s 和 goal 不同,找到两个不同的字符位置并交换,检查交换后是否相同。
*/

import java.util.stream.IntStream;
import java.util.stream.Collectors;

public class Solution {
    public boolean buddyStrings(String s, String goal) {
        if (s.length() != goal.length()) return false;
        if (s.equals(goal)) {
            long distinctCount = s.chars().distinct().count();
            return distinctCount < s.length();
        }

        int[] diff = IntStream.range(0, s.length())
                               .filter(i -> s.charAt(i) != goal.charAt(i))
                               .toArray();

        return diff.length == 2 &&
               s.charAt(diff[0]) == goal.charAt(diff[1]) &&
               s.charAt(diff[1]) == goal.charAt(diff[0]);
    }
}

解释

方法:

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

时间复杂度:

O(n)

空间复杂度:

O(k)

代码细节讲解

🦆
在算法中,如果s和goal完全相同且没有重复字符,返回False的逻辑是怎样的?为什么即使完全相同也需要至少有一个重复字符才能返回True?
当s和goal完全相同时,题目要求通过交换两个字符使得s等于goal。如果s中所有字符都是唯一的,那么交换任何两个字符都会改变s的内容,导致s不再与goal相同。因此,只有当s中至少有一个字符出现两次或更多时,我们才能通过交换这两个相同的字符,使得s在视觉上看起来仍然保持不变,满足题目的要求。如果没有重复字符,即使s和goal完全相同,也无法通过这样的交换达到题目要求的效果,因此算法返回False。
🦆
题解提到如果不匹配的位置不是两处就返回False,能否详细解释一下为什么只有两处不匹配时才能通过一次交换解决问题?
如果s与goal之间的不匹配位置超过两处或少于两处,无法仅通过一次交换使两个字符串相等。如果只有一处不匹配,无法找到另一处进行有效的交换。如果有三处或更多不匹配,一次交换(即交换两个字符的位置)无法同时纠正所有不匹配的位置。因此,只有当恰好有两处字符不匹配时,我们可以尝试交换s中这两处不匹配的字符,检查交换后s是否能变为goal。如果交换后两处字符都能匹配上对方原位置的字符,则说明一次交换可以解决问题,否则不行。
🦆
在解决不匹配的两个字符时,直接比较了这两个字符的目标位置是否符合要求,这种方法是否总是有效,或者存在某些特殊情况下会导致错误的结果?
这种方法在大多数情况下是有效的,因为它直接检查了通过一次交换能否解决两处不匹配的问题。具体来说,如果s中的第一个不匹配字符可以与goal中的第二个不匹配字符交换,并且s中的第二个不匹配字符也可以与goal中的第一个不匹配字符交换,那么一次交换就能使s变为goal。这种检查是基于题目设定的,即只能进行一次交换。不存在特殊情况会导致这种检查方法出错,只要保证不匹配的位置恰好有两处,并且这两处可以互换,就可以确保算法的正确性。

相关问题