LeetCode 859. 亲密字符串

2024-11-02 HGNULB 约 9 分钟

文章信息 7 个分类 · 2 个标签

分类

LeetCode CodeTop 简单 未解决 2-5 滴滴 华为

标签

字符串 哈希表

目录 收起 展开

题目描述

✅ 859. 亲密字符串

题意分析

给两个只含小写字母的字符串 s 和 goal，问能不能在 s 上恰好执行一次交换，使它变成 goal。交换的两个下标 $i$ 和 $j$ 必须不同，但两个位置上的字符可以相同。

「恰好一次」这四个字是整道题的题眼，它带来两个后果。第一，不能选择「一次都不换」，所以 s 和 goal 本来就相等时并不能直接返回真。第二，因为下标必须不同、但字符可以相同，所以在 s 里交换两个相同的字符是一次合法却不改变结果的操作——这恰好给「本来就相等」的情形留了一条生路。

一次交换最多改动两个位置，这是最强的结构约束：s 和 goal 的不同位置数量只可能是 0 或 2，别的数字一律无解。数量为 1 是不可能的，因为交换要么同时改两个位置，要么一个都不改。

长度不等时无论如何都不可能相等，必须在最前面挡住，否则后续的逐位比较会越界。

规模上两串长度都不超过 $2 \times 10^4$，字符集只有 26 个小写字母，一次线性扫描加一个长度 26 的计数数组就足够，不需要任何额外数据结构。

边界上要单独想清楚三种输入：两串完全相同且含重复字符（如 "aa" 与 "aa"）、两串完全相同但字符两两不同（如 "ab" 与 "ab"）、以及差异恰好两处却无法通过交换对上（如 "abcd" 与 "aecf"）。

解法：模拟交换

核心思路

最朴素的做法是照定义枚举：对所有 $i < j$ 交换 s 的第 $i$ 位和第 $j$ 位，再和 goal 比一次。这是 $O(n^3)$，或者用「只比较受影响的两位」优化到 $O(n^2)$。$n$ 到 $2 \times 10^4$ 时平方级已经吃力，更重要的是这个做法完全没有利用「一次交换只动两个位置」这个强得离谱的结构。

瓶颈就在这里：我们在盲目枚举交换，而实际上交换的位置根本不用猜——如果 s 和 goal 有不同的位置，那么被交换的两个下标必然就是这些不同位置本身。因为没被交换的下标在交换前后字符不变，它若和 goal 不同，交换后依然不同。

由此得到分类讨论的骨架。设 $D = {i : s_i \ne goal_i}$ 为差异位置集合。

当 $

D

= 0$，即两串已经相同。这时任何交换都会破坏相等，除非交换的两个位置上字符恰好一样。所以判据是「s 中是否存在某个字母出现至少两次」。用一个长度 26 的计数数组扫一遍即可，一旦某个计数达到 2 就可以立刻返回真。

当 $

D

= 2$，设两个差异位置为 $p$ 和 $q$。唯一可能的交换就是把 $s_p$ 和 $s_q$ 换过来，换完之后 $p$ 位变成 $s_q$、$q$ 位变成 $s_p$，要求它们分别等于 $goal_p$ 和 $goal_q$。所以判据是 $s_p = goal_q$ 且 $s_q = goal_p$，这一对交叉相等既是必要条件也是充分条件。

当 $

D

= 1$ 或 $

D

> 2$，一律返回假。前者不可能由一次交换产生，后者超出了一次交换能修补的位数。

于是扫描过程只需要维护两个变量 first 和 second，含义固定为「目前遇到的第一个、第二个差异位置的下标，尚未遇到则为 $-1$」。这个不变量让我们在遇到第三个差异位置的瞬间就能提前返回假，不必扫完全串。

解题步骤

• 先比长度，不等直接返回假。为什么必须放在最前：后面所有的逐位比较都假定两串下标范围一致，不挡住会越界。
• 判断两串是否完全相等。相等时走「重复字符」分支：用长度 26 的计数数组扫一遍 s，某个字母的计数一旦达到 2 就返回真，扫完仍没有则返回假。为什么不能直接返回真：题目要求恰好交换一次，没有重复字符时任何一次交换都必然破坏相等。
• 为什么这个分支里可以只看 s 不看 goal：既然两串已经完全相同，它们的字符多重集当然也相同，看谁都一样。
• 不相等时进入通用分支，用 first、second 两个变量记录差异位置，初值都设为 $-1$。逐位比较，遇到差异时按顺序填入 first、second；如果两个都已经被填过还遇到第三个差异，立刻返回假。为什么可以提前返回：差异超过两处时一次交换绝对补不齐，继续扫描没有任何信息增量。
• 扫描结束后先检查 second != -1。为什么要检查：差异恰好一处时 second 仍是 $-1$，此时若直接用它当下标会越界；而且一处差异本身就是无解的信号。
• 最后验证交叉相等：s[first] == goal[second] 且 s[second] == goal[first]。为什么这一步不能省：差异位置数对了不代表换过来就能对上，交换只是把两个字符对调，字符本身不会改变。
• 以 s = "abcd"、goal = "abdc" 走一遍：长度都是 4，通过；两串不相等，进入通用分支。first = second = -1。$i=0$，'a' 对 'a' 相同，跳过。$i=1$，'b' 对 'b' 相同，跳过。$i=2$，'c' 对 'd' 不同，first 被填成 2。$i=3$，'d' 对 'c' 不同，first 已占用，second 被填成 3。扫描结束，second 已经是 3 而不是 $-1$，通过检查。交叉验证：s[2] = 'c' 与 goal[3] = 'c' 相等，s[3] = 'd' 与 goal[2] = 'd' 相等，两条都成立，返回 true。
• 再看相等分支的走法：s = goal = "aabb" 时，长度相同、两串相等，进入计数分支；扫到 $i=0$ 时 'a' 的计数变成 1，扫到 $i=1$ 时 'a' 的计数变成 2，超过阈值，立即返回 true——对应的操作就是交换下标 0 和 1 这两个相同的 'a'。若换成 s = goal = "ab"，'a'、'b' 的计数各为 1，扫完没有触发，返回 false。

代码实现

// 若字符串相等，必须存在至少一个重复字符，才能交换后仍相等。
class Solution {
    public boolean buddyStrings(String s, String goal) {
        if (s.length() != goal.length()) {
            return false;
        }

        if (s.equals(goal)) {
            int[] cnt = new int[26];
            for (char ch : s.toCharArray()) {
                cnt[ch - 'a']++;
                if (cnt[ch - 'a'] > 1) {
                    return true;
                }
            }
            return false;
        }

        int first = -1;
        int second = -1;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != goal.charAt(i)) {
                if (first == -1) {
                    first = i;
                } else if (second == -1) {
                    second = i;
                } else {
                    return false;
                }
            }
        }

        return second != -1
                && s.charAt(first) == goal.charAt(second)
                && s.charAt(second) == goal.charAt(first);
    }
}

// 若字符串相等，必须存在至少一个重复字符，才能交换后仍相等。
func buddyStrings(s string, goal string) bool {
    if len(s) != len(goal) {
        return false
    }

    if s == goal {
        var cnt [26]int
        for i := 0; i < len(s); i++ {
            idx := s[i] - 'a'
            cnt[idx]++
            if cnt[idx] > 1 {
                return true
            }
        }
        return false
    }

    first := -1
    second := -1
    for i := 0; i < len(s); i++ {
        if s[i] != goal[i] {
            if first == -1 {
                first = i
            } else if second == -1 {
                second = i
            } else {
                return false
            }
        }
    }

    return second != -1 && s[first] == goal[second] && s[second] == goal[first]
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是字符串长度。长度比较是常数级；相等判断扫一遍；相等分支的计数扫一遍且可能提前返回；通用分支的差异定位扫一遍且遇到第三处差异时提前返回。三条路径都只做常数次线性扫描。
• 空间复杂度：$O(1)$。相等分支用了一个长度固定为 26 的计数数组，与输入规模无关；通用分支只有 first、second 两个下标变量，没有任何随 $n$ 增长的结构。

关键点总结

• 「恰好操作一次」和「至多操作一次」是完全不同的题面，前者必须为「输入已经满足目标」单独设计一条判据。本题的这条判据是「存在重复字符」，它把「必须动一次手」和「不能改变结果」两个矛盾的要求同时满足了。
• 当一次操作只能影响常数个位置时，被操作的位置是可以被反推出来的，不需要枚举。这个思路可以推广到「一次翻转」「一次删除」「一次替换」这一整类题。
• 差异位置数量为 1 是不可能的——交换的对称性决定了受影响位置要么是 0 个要么是 2 个。能主动说出这条奇偶性，说明真的想清楚了操作的结构。
• 定位到两处差异之后，交叉相等 $s_p = goal_q \wedge s_q = goal_p$ 是充要条件，不是启发式。必要性来自「其余位置必须已经相同」，充分性来自「交换后这两位刚好互换」。
• 面试视角：这题标着简单，但通过率不高，卡的全是分类讨论的完备性。答题时先把差异位置数量按 0、1、2、大于 2 四类列全，再逐类给判据，比直接写代码更能体现严谨性。

易错点总结

• 错误写法：漏掉开头的长度比较。用例 s = "ab"、goal = "abc" 会在逐位比较时越界抛异常，或在某些写法下把长度不同的串误判成有两处差异。
• 错误写法：两串相等时直接返回 true。用例 s = "ab"、goal = "ab" 里没有任何重复字符，交换 'a' 和 'b' 之后变成 "ba"，不再等于 goal，正确答案是 false。
• 错误写法：完全不处理两串相等的情况，只走差异定位分支。用例 s = "aa"、goal = "aa" 的差异数为 0，second 停在 $-1$，函数返回 false，但正确答案是 true。
• 错误写法：允许差异位置只有一处也返回真。用例 s = "ab"、goal = "aa" 只有下标 1 不同，一次交换必然同时改动两位，正确答案是 false。
• 错误写法：数到两处差异就直接返回真，不做交叉验证。用例 s = "abcd"、goal = "aecf" 的差异在下标 1 和 3，但 s[1] = 'b' 并不等于 goal[3] = 'f'，交换后仍然对不上，正确答案是 false。
• 错误写法：交叉验证写成同侧比较 s[first] == goal[first] && s[second] == goal[second]。这两个位置本来就是差异位置，条件恒为假，所有输入都会返回 false。
• 错误写法：相等分支用集合判重复时把条件写成 set.size() <= s.length()。这个不等式恒成立，任何相等输入都会返回真，"ab" 与 "ab" 就会错判。
• 错误写法：遇到第三处差异时只 break 而不返回，随后仍拿 first、second 做交叉验证。用例 s = "abcd"、goal = "badc" 有四处差异，前两处恰好满足交叉相等，会被错判成 true。

相似题目

题目	难度	考察点
242. 有效的字母异位词	简单	只比较字符多重集是否一致，完全不关心位置，用一个计数数组做加减即可判定
205. 同构字符串	简单	考的是位置对齐下的字符双向映射一致性，需要两张映射表互相校验，而不是数差异个数
1657. 确定两个字符串是否接近	中等	允许任意多次操作，判据升级为「字符集合相同且频次的多重集相同」，考察的是不变量的提炼