LeetCode 859. 亲密字符串

约 5 分钟
文章信息 7 个分类 2 个标签
分类
LeetCode CodeTop 简单 未解决 2-5 华为 滴滴
标签
字符串 哈希表

题目描述

✅ 859. 亲密字符串

image-20260928225216289

image-20260928225216290

题意分析

必须在 s 中选两个不同下标交换一次，使结果等于 goal。交换不改变长度，两个下标上的字符却可以相同；所以字符串已经相等时，也要判断能否完成这次交换。

解法：模拟交换

核心思路

[!blue]

先排除长度不同的情况。若两串不相等，要改变结果就必须交换两个不同字符，这恰好改变两个位置，其他位置全部不动。因此两串必须恰好有两处差异，记为 first 和 second；只有一处差异无法单独修复，超过两处也不可能由一次交换解决。

差异数为 2 仍然不够。交换后第一个位置放入原来的第二个字符，第二个位置放入原来的第一个字符，所以还必须满足 s[first] == goal[second] 且 s[second] == goal[first]。其余位置原本就相同，这两个条件成立便能保证整串相等。

若两串原本相等，交换不同字符会破坏相等关系，只有交换两个相同字符才能保持结果不变。题目字符均为小写英文字母，用 26 个计数位置判断是否存在重复字符即可。没有重复字符，或者字符串只有一个字符，都无法完成要求的交换。

解题步骤

  1. 长度不同直接返回 false。
  2. 若 s == goal，统计字符频次，首次发现重复字符就返回 true；全部字符都不同则返回 false。
  3. 否则扫描两串，记录前两处差异。发现第三处差异时立即返回 false。
  4. 扫描结束后，先确认第二处差异存在，再验证两处字符交叉匹配。短路判断也保证不会访问尚未赋值的下标。

代码实现

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$ 为字符串长度，比较和扫描均为线性过程。
  • 空间复杂度：Go 辅助空间 $O(1)$；当前 Java 相等分支的字符数组转换占 $O(n)$，计数表本身为常数。

关键点总结

[!green]

  • 恰好一次不同于至多一次，不能对相等输入直接成功。
  • 定位两处差异后仍需验证交换能修复它们。

易错点总结

[!yellow]

  • 相等时一律返回真，会错误接受没有重复字符的字符串。
  • 只数两处差异而不交叉验证，会接受无法互换的字符。
  • 第三处差异仅退出扫描而不失败，会忽略剩余不匹配。

相似题目

题目 难度 关联与区别
854. 相似度为 K 的字符串 困难 原题求最少任意交换次数，本题恰好只交换两个位置，还要单独考虑原串已经相同的情况。
242. 有效的字母异位词 简单 频次相同是交换可达的必要条件，但本题只允许一次交换，异位词条件本身并不足够。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2024/54008582
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！