[leetcode 859] 亲密字符串
[leetcode 859] 亲密字符串

Problem:

859. 亲密字符串

给定两个由小写字母构成的字符串 AB ,只要我们可以通过交换 A 中的两个字母得到与 B 相等的结果,就返回 true ;否则返回 false

示例 1:

输入: A = "ab", B = "ba"
输出: true

示例 2:

输入: A = "ab", B = "ab"
输出: false

示例 3:

输入: A = "aa", B = "aa"
输出: true

示例 4:

输入: A = "aaaaaaabc", B = "aaaaaaacb"
输出: true

示例 5:

输入: A = "", B = "aa"
输出: false

提示:

  1. 0 <= A.length <= 20000
  2. 0 <= B.length <= 20000
  3. AB 仅由小写字母构成。

Solution:

这道题需要我们判断的情况很多,如上面的思维导图所示,第一判断条件是字符串长度是否相同,不相同肯定不是兄弟字符串,如果相同,进行正常的判断逻辑。

如果两个字符串相等

因为还是需要进行一步交换操作,所以就要保证,字符串中必须包含两个以上的相同字符串,比如:aab 或者 aaa 此类的字符串。

如果两个字符串不相等

因为是一步交换,所以必须要保证,两个字符串对比,有且只有两个不同的字符,找到这两个字符,交换位置,如果相同,表示为兄弟字符串。

时间复杂度O(N)

func buddyStrings(A string, B string) bool {
	isBuddyStrings := true
	var diffA []string
	var diffB []string
	var isSameWordExistedString bool

	// 如果两个字符串长度不同,不是兄弟字符串
	if len(diffA) != len(diffB) {
		return false
	}

	tempStrMap := make(map[string]bool)
	for i := 0; i < len(A); i++ {
		// 每个位置不相同的字符
		if A[i] != B[i] {
			diffA = append(diffA, string(A[i]))
			diffB = append(diffB, string(B[i]))
		}

		// 判断有没有出现两个以上相同字符
		_, existed := tempStrMap[string(A[i])]
		if existed {
			isSameWordExistedString = true
		}
		tempStrMap[string(A[i])] = true
	}

	// 如果两个字符串相同,判断是否包含相同字母
	if len(diffA) == 0 && len(diffB) == 0 {
		if isSameWordExistedString {
			return true
		}

		return false
	}

    // 如果两个字符串不相同,判断是不是有且只有两个不同字符
	if len(diffA) != 2 && len(diffB) != 2 {
		return false
	}
	
    // 如果两个字符串不相同,判断交换后的字符是不是相同
	if diffA[0] != diffB[1] || diffA[1] != diffB[0] {
		return false
	}

	return isBuddyStrings
}


If You Have Any Question, You Can Contact Me Through liam@blue7wings.com, @Blue7Wings, #Liam_Hsia