给你两个字符串 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 相等。
示例 4：
输入：s = "aaaaaaabc", goal = "aaaaaaacb"
输出：true
提示：
1 <= s.length, goal.length <= 2 * 104
s 和 goal 由小写英文字母组成
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/buddy-strings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
package cn.fansunion.leecode.string;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
/**
* 859. 亲密字符串<br/>
* 给你两个字符串 s 和 goal ，只要我们可以通过交换 s 中的两个字母得到与 goal 相等的结果，就返回 true ； 否则返回 false 。<br/>
*
* 交换字母的定义是：取两个下标 i 和 j （下标从 0 开始）且满足 i != j ，接着交换 s[i] 和 s[j] 处的字符。<br/>
*
* 例如，在 "abcd" 中交换下标 0 和下标 2 的元素可以生成 "cbad" 。<br/>
*
* 来源：力扣（LeetCode） 链接：力扣 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*
* @author [email protected]
*
* 2022-2-19
*/
public class BuddStrings {
/*示例 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 相等。
示例 4：
输入：s = "aaaaaaabc", goal = "aaaaaaacb"
输出：true
提示：
1 <= s.length, goal.length <= 2 * 104
s 和 goal 由小写英文字母组成*/
/**
* 按照题目意思和定义，正常交换，再比较（时间复杂度：O(N*N)）leecode超时了
* @param s
* @param goal
* @return
*/
public boolean buddyStrings(String s, String goal) {
//false的情况
if(s==null || goal== null) {
return false;
}
if(s.length() != goal.length()) {
return false;
}
//排序后，不相同，也不可能
char[] charArray1=s.toCharArray();
char[] charArray2=goal.toCharArray();
Arrays.sort(charArray1);
Arrays.sort(charArray2);
if(!Arrays.equals(charArray1, charArray2)) {
return false;
}
//正常情况，交换一次再比较
for (int i = 0; i < s.length(); i++) {
for (int j = 1; j < s.length(); j++) {
if (i != j) {
//产生新的char
char[] chars = s.toCharArray();
swap(chars, i, j);
if (Arrays.equals(chars, goal.toCharArray())) {
return true;
}
}
}
}
return false;
}
private void swap(char[] chars, int i, int j) {
char tmp = chars[i];
chars[i] = chars[j];
chars[j] = tmp;
}
/**
* 尝试创新解法：用O(n)解法
* @param s
* @param goal
* @return
*/
public boolean buddyStringsGood(String s, String goal) {
//false的情况
if(s==null || goal== null) {
return false;
}
if(s.length() != goal.length()) {
return false;
}
//排序后，不相同，也不可能
char[] charArray1=s.toCharArray();
char[] charArray2=goal.toCharArray();
Arrays.sort(charArray1);
Arrays.sort(charArray2);
if(!Arrays.equals(charArray1, charArray2)) {
return false;
}
//不排序，比较2个数组的区别
int difSize=0;
//2个字符串，不同字母的索引位置
int[] difIndex=new int[s.length()];
for (int index = 0; index < s.length(); index++) {
if(s.charAt(index)!=goal.charAt(index)) {
//记录前2次
difIndex[difSize]=index;
difSize++;
//不相同的字符有3次+，肯定不匹配了
if(difSize>=3) {
break;
}
}
}
//超过2次，达到3次，肯定不行了
if(difSize>=3) {
return false;
}
//正常的交换情况，得对称
else if(difSize==2) {
final int dif0Index = difIndex[0];
final int dif1Index = difIndex[1];
if(s.charAt(dif0Index) == goal.charAt(dif1Index) &&s.charAt(dif1Index) == goal.charAt(dif0Index) ) {
return true;
}else {
return false;
}
}
//只有1次，也不行
else if(difSize==1) {
return false;
}
//aba,abba,aabb,abbc可以；abcd就不行
//1个字符串，在交换1次之后，仍然完全一样；说明字符串，至少有2个一样的字符
else if(difSize==0) {
boolean existSame=existSame(goal);
if(existSame) {
return true;
}else {
return false;
}
}
return false;
}
private boolean existSame(String goal) {
Set<Character> set = new HashSet<>();
final char[] charArray = goal.toCharArray();
for(char ch:charArray) {
set.add(ch);
}
return set.size()!=goal.length();
}
}
package test.leecode.string;标签：return,goal,3621,buddyStringsGood,Assert,亲密,bs,字符串,false From： https://blog.51cto.com/fansunion/6056784
import org.junit.Assert;
import org.junit.Test;
import cn.fansunion.leecode.string.BuddStrings;
/**
* @author [email protected]
*
* 2022-2-19
*/
public class BuddStringsTest {
@Test
public void test() {
BuddStrings bs = new BuddStrings();
Assert.assertTrue(bs.buddyStrings("ab", "ba"));
Assert.assertTrue(bs.buddyStrings("aa", "aa"));
Assert.assertTrue(bs.buddyStrings("aaaaaaabc", "aaaaaaacb"));
Assert.assertTrue(bs.buddyStrings("aba", "aba"));
Assert.assertTrue(bs.buddyStrings("aba", "aba"));
Assert.assertFalse(bs.buddyStrings("ab", "ab"));
Assert.assertFalse(bs.buddyStrings("abc", "abc"));
Assert.assertFalse(bs.buddyStrings("a", "a"));
Assert.assertFalse(bs.buddyStrings("abcd", "dcba"));
Assert.assertFalse(bs.buddyStrings("abcdabcd", "abcdabdcd"));
}
@Test
public void testBuddyStringsGood() {
BuddStrings bs = new BuddStrings();
Assert.assertTrue(bs.buddyStringsGood("acccccb", "bccccca"));
Assert.assertTrue(bs.buddyStringsGood("ab", "ba"));
Assert.assertTrue(bs.buddyStringsGood("aa", "aa"));
Assert.assertTrue(bs.buddyStringsGood("aaaaaaabc", "aaaaaaacb"));
Assert.assertTrue(bs.buddyStringsGood("aba", "aba"));
Assert.assertTrue(bs.buddyStringsGood("aba", "aba"));
Assert.assertFalse(bs.buddyStringsGood("ab", "ab"));
Assert.assertFalse(bs.buddyStringsGood("abc", "abc"));
Assert.assertFalse(bs.buddyStringsGood("a", "a"));
Assert.assertFalse(bs.buddyStringsGood("abcd", "dcba"));
Assert.assertFalse(bs.buddyStringsGood("abcdabcd", "abcdabdcd"));
}
}