What is the primary technique to solve the 'Check if One String Swap Can Make Strings Equal' problem?

The primary technique involves counting the mismatched character positions between the two strings and checking if exactly two mismatches exist, then verifying if swapping those characters will make the strings equal.

What happens if the two strings are already equal in the 'Check if One String Swap Can Make Strings Equal' problem?

If the strings are already equal, no swap is needed, and the answer is true immediately.

How does the mismatch counting strategy help in solving the problem?

Counting mismatched positions helps quickly determine if it's even possible to make the strings equal with one swap. If the number of mismatches is not 0 or 2, it's impossible to make the strings equal with one swap.

What is the time complexity of the 'Check if One String Swap Can Make Strings Equal' problem?

The time complexity is O(N) because we iterate through both strings to identify mismatches, where N is the length of the strings.

What should be done if the number of mismatched positions is more than 2?

If there are more than two mismatched positions, it is impossible to make the strings equal with just one swap, so the answer should be false.

#1790

Easy

auto_awesome哈希·表·结合·string

LeetCode 题解工作台

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

给你长度相等的两个字符串 s1 和 s2 。一次字符串交换操作的步骤如下：选出某个字符串中的两个下标（不必不同），并交换这两个下标所对应的字符。如果对其中一个字符串执行最多一次字符串交换就可以使两个字符串相等，返回 true ；否则，返回 false 。示例 1：输入： s1 = …

哈希表字符串计数

题目描述

给你长度相等的两个字符串 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 仅由小写英文字母组成

lightbulb

解题思路

方法一：计数

我们用变量 $cnt$ 记录两个字符串中相同位置字符不同的个数，两个字符串若满足题目要求，那么 $cnt$ 一定为 $0$ 或 $2$ 。另外用两个字符变量 $c1$ 和 $c2$ 记录两个字符串中相同位置字符不同的字符。

同时遍历两个字符串，对于相同位置的两个字符 $a$ 和 $b$ ，如果 $a \ne b$ ，那么 $cnt$ 自增 $1$ 。如果此时 $cnt$ 大于 $2$ ，或者 $cnt$ 为 $2$ 且 $a \ne c2$ 或 $b \ne c1$ ，那么直接返回 false。注意记录一下 $c1$ 和 $c2$ 。

遍历结束，若 $cnt \neq 1$ ，返回 true。

时间复杂度 $O(n)$ ，其中 $n$ 为字符串长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def areAlmostEqual(self, s1: str, s2: str) -> bool:
        cnt = 0
        c1 = c2 = None
        for a, b in zip(s1, s2):
            if a != b:
                cnt += 1
                if cnt > 2 or (cnt == 2 and (a != c2 or b != c1)):
                    return False
                c1, c2 = a, b
        return cnt != 1

speed

复杂度分析

指标	值
时间	O(N)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
The candidate should efficiently identify mismatched character positions.
question_mark
The candidate should recognize the importance of string length and how to handle identical strings directly.
question_mark
The candidate should avoid unnecessary operations, focusing on counting mismatches and validating potential swaps.

warning

常见陷阱

外企场景

error
Confusing the number of mismatches, which must be 0 or 2 for a valid swap.
error
Not checking if swapping characters at mismatched positions results in the strings becoming equal.
error
Failing to handle the case where the strings are already equal.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Handling cases with different character sets, not just lowercase letters.
arrow_right_alt
Considering cases with larger strings where performance may be more important.
arrow_right_alt
Handling strings with more complex structures or patterns beyond simple swaps.

help

常见问题

外企场景

继续练习

#1781 所有子字符串美丽值之和 #1737 满足三条件之一需改变的最少字符数 #1876 长度为三且各字符不同的子字符串