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哥：赞👍🏻！
网友评论