跳至主要內容

1790. 仅执行一次字符串交换能否使两个字符串相等


1790. 仅执行一次字符串交换能否使两个字符串相等

🟢   🔖  哈希表 字符串 计数  🔗 力扣open in new window LeetCodeopen in new window

题目

You are given two strings s1 and s2 of equal length. A string swap is an operation where you choose two indices in a string (not necessarily different) and swap the characters at these indices.

Return true if it is possible to make both strings equal by performing at most one string swap on exactly one of the strings. Otherwise, return false.

Example 1:

Input: s1 = "bank", s2 = "kanb"

Output: true

Explanation: For example, swap the first character with the last character of s2 to make "bank".

Example 2:

Input: s1 = "attack", s2 = "defend"

Output: false

Explanation: It is impossible to make them equal with one string swap.

Example 3:

Input: s1 = "kelb", s2 = "kelb"

Output: true

Explanation: The two strings are already equal, so no string swap operation is required.

Constraints:

  • 1 <= s1.length, s2.length <= 100
  • s1.length == s2.length
  • s1 and s2 consist of only lowercase English letters.

题目大意

给你长度相等的两个字符串 s1s2 。一次字符串交换 操作的步骤如下:选出某个字符串中的两个下标(不必不同),并交换这两个下标所对应的字符。

如果对 其中一个字符串 执行 最多一次字符串交换 就可以使两个字符串相等,返回 true ;否则,返回 false

示例 1:

输入: s1 = "bank", s2 = "kanb"

输出: true

解释: 例如,交换 s2 中的第一个和最后一个字符可以得到 "bank"

示例 2:

输入: s1 = "attack", s2 = "defend"

输出: false

解释: 一次字符串交换无法使两个字符串相等

示例 3:

输入: s1 = "kelb", s2 = "kelb"

输出: true

解释: 两个字符串已经相等,所以不需要进行字符串交换

示例 4:

输入: s1 = "abcd", s2 = "dcba"

输出: false

提示:

  • 1 <= s1.length, s2.length <= 100
  • s1.length == s2.length
  • s1s2 仅由小写英文字母组成

解题思路

  1. 相等情况判断

    • 首先检查 s1s2 是否相等。如果相等,直接返回 true,因为没有任何交换需要进行。
  2. 找出不同的字符

    • 遍历两个字符串 s1s2,记录下它们不相等的字符。将这两个字符串不同的位置的字符依次加入 res 数组中。
  3. 检查交换条件

    • 如果不同的字符的数量是 4(意味着有两个字符的交换),则需要检查:
      • res[0] == res[3]:即 s1 中不相等的字符和 s2 中交换的位置的字符是否相等。
      • res[1] == res[2]:即 s1 中不相等的字符和 s2 中交换的位置的字符是否相等。
    • 如果这两个条件都满足,则返回 true,表示通过一次交换可以使 s1s2 相等。
  4. 返回结果

    • 如果以上条件不满足,则返回 false

复杂度分析

  • 时间复杂度O(n),其中 n 是字符串的长度,遍历了字符串 s1s2 一次。
  • 空间复杂度O(1),使用了一个 res 数组来存储不同的字符,长度最长为 4

代码

/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var areAlmostEqual = function (s1, s2) {
	if (s1 == s2) return true;
	let res = [];
	for (let i = 0; i < s2.length; i++) {
		if (s1[i] !== s2[i] && res.length < 3) {
			res.push(s1[i]);
			res.push(s2[i]);
		}
	}
	return res.length == 4 && res[0] == res[3] && res[1] == res[2];
};

相关题目

题号标题题解标签难度力扣
859亲密字符串[✓]哈希表 字符串🟢🀄️open in new window 🔗open in new window
2531使字符串中不同字符的数目相等哈希表 字符串 计数🟠🀄️open in new window 🔗open in new window
3265统计近似相等数对 I数组 哈希表 计数 2+🟠🀄️open in new window 🔗open in new window