1790. 仅执行一次字符串交换能否使两个字符串相等
1790. 仅执行一次字符串交换能否使两个字符串相等
题目
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
ands2
consist of only lowercase English letters.
题目大意
给你长度相等的两个字符串 s1
和 s2
。一次字符串交换 操作的步骤如下:选出某个字符串中的两个下标(不必不同),并交换这两个下标所对应的字符。
如果对 其中一个字符串 执行 最多一次字符串交换 就可以使两个字符串相等,返回 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
s1
和s2
仅由小写英文字母组成
解题思路
相等情况判断:
- 首先检查
s1
和s2
是否相等。如果相等,直接返回true
,因为没有任何交换需要进行。
- 首先检查
找出不同的字符:
- 遍历两个字符串
s1
和s2
,记录下它们不相等的字符。将这两个字符串不同的位置的字符依次加入res
数组中。
- 遍历两个字符串
检查交换条件:
- 如果不同的字符的数量是 4(意味着有两个字符的交换),则需要检查:
res[0] == res[3]
:即s1
中不相等的字符和s2
中交换的位置的字符是否相等。res[1] == res[2]
:即s1
中不相等的字符和s2
中交换的位置的字符是否相等。
- 如果这两个条件都满足,则返回
true
,表示通过一次交换可以使s1
和s2
相等。
- 如果不同的字符的数量是 4(意味着有两个字符的交换),则需要检查:
返回结果:
- 如果以上条件不满足,则返回
false
。
- 如果以上条件不满足,则返回
复杂度分析
- 时间复杂度:
O(n)
,其中n
是字符串的长度,遍历了字符串s1
和s2
一次。 - 空间复杂度:
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 | 亲密字符串 | [✓] | 哈希表 字符串 | 🟢 | 🀄️ 🔗 |
2531 | 使字符串中不同字符的数目相等 | 哈希表 字符串 计数 | 🟠 | 🀄️ 🔗 | |
3265 | 统计近似相等数对 I | 数组 哈希表 计数 2+ | 🟠 | 🀄️ 🔗 |