教3妹学编程-859. 亲密字符串

2哥：3妹，别看肥皂剧了，今天我们来做一个算法题。

3妹关掉了电视，高兴的跑过来。
3妹：好呀好呀，java的数据结构我已经全部学完了，尽管放马过来吧。

题目

给你两个字符串 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^4
s 和 goal 由小写英文字母组成

思路：

3妹： 根据题目里的示例， 这个题要分两种情况，一种是s和goal相等的情况，如果s和goal相等， 则需要s中有两个字符相等，这样才能保证交换后依然不变；还有一种是s和gaol不相等，这个时候要遍历每个字符，找到不相等字符的两个位置，看看交换后是否相等。
2哥：不错不错，思路很清晰，那试差写一下吧。

java代码：

class Solution {
   public boolean buddyStrings(String s, String goal) {
        if (s.length() != goal.length()) {
            return false;
        }

        if (s.equals(goal)) {
            //如果s和goal相等， 则需要s中有两个字符相等，交换后依然不变
            int[] count = new int[26];
            for (int i = 0; i < s.length(); i++) {
                count[s.charAt(i) - 'a']++;
                if (count[s.charAt(i) - 'a'] > 1) {
                    return true;
                }
            }
            return false;
        } else {
            int first = -1;
            int second = -1;
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) != goal.charAt(i)) {
                    if (first < 0) {
                        first = i;
                    } else if (second < 0) {
                        second = i;
                    } else {
                        return false;
                    }
                }
            }
            return second >= 0 && s.charAt(first) == goal.charAt(second) && s.charAt(second) == goal.charAt(first); //这里不用重新组装字符串，只需要比较不相等位置的两个字符，是否等于目标字符串位置的字符就好了
        }

    }
}

复杂度分析

2哥：看来3妹进度很大嘛，那能分析下这种解法的时间复杂度是多少吗？

3妹：emmm,
时间复杂度：O(N)，其中 N为字符串的长度。我们至多遍历字符串两遍。

空间复杂度：O(C)。需要常数个空间保存字符串的字符统计次数，我们统计所有小写字母的个数，因此 C = 26。

2哥：赞👍🏻！