859. 亲密字符串

🟢   🔖  哈希表 字符串  🔗 力扣 LeetCode

题目

Given two strings s and goal, return true if you can swap two letters ins so the result is equal togoal , otherwise, returnfalse .

Swapping letters is defined as taking two indices i and j (0-indexed) such that i != j and swapping the characters at s[i] and s[j].

• For example, swapping at indices 0 and 2 in "abcd" results in "cbad".

Example 1:

Input: s = "ab", goal = "ba"

Output: true

Explanation: You can swap s[0] = 'a' and s[1] = 'b' to get "ba", which is equal to goal.

Example 2:

Input: s = "ab", goal = "ab"

Output: false

Explanation: The only letters you can swap are s[0] = 'a' and s[1] = 'b', which results in "ba" != goal.

Example 3:

Input: s = "aa", goal = "aa"

Output: true

Explanation: You can swap s[0] = 'a' and s[1] = 'a' to get "aa", which is equal to goal.

Constraints:

• 1 <= s.length, goal.length <= 2 * 10^4
• s and goal consist of lowercase letters.

题目大意

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

解题思路

解题思路

题目要求判断字符串 s 是否可以通过一次交换两个字母变成字符串 goal，可以分为以下几种情况进行分析：

1. 两个字符串长度不同

   如果 s.length !== goal.length，那么不可能通过交换得到相等的字符串，直接返回 false。

2. 两个字符串完全相等

   • 如果 s === goal，通过 Set 检查是否存在重复字符，若有则返回 true，否则返回 false。
   • 原因是，当两个字符串完全相同时，只有在存在重复字符的情况下，我们可以交换这两个重复字符，使字符串不变。
   • 例如：s = "aabb", goal = "aabb"，交换两个 a 或两个 b。
   • 如果字符串没有重复字符，例如 s = "abc", goal = "abc"，则无法通过一次交换使字符串不变。

3. 两个字符串不同

   • 如果 s !== goal，则需要满足以下条件：
     1. 两个字符串中恰好有两个位置的字符不同。
     2. 这两个位置的字符交换后，s 能够变成 goal。
   • 遍历两个字符串，找出所有不同位置的下标。
   • 如果不同位置的数量不等于 2，返回 false。
   • 检查这两个位置的字符是否能够通过交换使两个字符串相等，即 s[i] === goal[j] 且 s[j] === goal[i]。

复杂度分析

• 时间复杂度：O(n)，遍历字符串的长度，进行比较和重复字符检查。
• 空间复杂度：O(n)，如果 s === goal 时，用到了一个 Set 来存储字符，空间复杂度为O(n)。

代码

/**
 * @param {string} s
 * @param {string} goal
 * @return {boolean}
 */
var buddyStrings = function (s, goal) {
	// 1. 长度不同直接返回 false
	if (s.length !== goal.length) return false;

	// 2. 当两个字符串相等时，检查是否有重复字符
	if (s === goal) {
		const seen = new Set();
		for (let char of s) {
			if (seen.has(char)) return true; // 存在重复字符
			seen.add(char);
		}
		return false; // 没有重复字符
	}

	// 3. 找出不同的字符位置
	let diff = [];
	for (let i = 0; i < s.length; i++) {
		if (s[i] !== goal[i]) {
			diff.push(i);
		}
	}

	// 4. 判断是否恰好有两个不同位置，且能通过交换使 s 和 goal 相等
	return (
		diff.length === 2 &&
		s[diff[0]] === goal[diff[1]] &&
		s[diff[1]] === goal[diff[0]]
	);
};

相关题目

题号	标题	题解	标签	难度	力扣
1657	确定两个字符串是否接近	[✓]	哈希表 字符串 计数 1+	🟠	🀄️ 🔗
1790	仅执行一次字符串交换能否使两个字符串相等	[✓]	哈希表 字符串 计数	🟢	🀄️ 🔗
2531	使字符串中不同字符的数目相等		哈希表 字符串 计数	🟠	🀄️ 🔗