解决方案
方法:情况列举
思路
如果 A[i] == B[i]
,我们就说 i
是匹配的,否则称 i
是不匹配的。亲密字符串几乎是完全匹配的,因为一次交换只会影响到两个索引。
如果交换 A[i]
和 A[j]
可以证明 A
和 B
是亲密字符串,那么就有 A[i] == B[j]
以及 A[j] == B[i]
。 这意味着在 A[i], A[j], B[i], B[j]
这四个自由变量中,只存在两种情况:A[i] == A[j]
或 A[i] != A[j]
算法
让我们来看看这些情况。
在 A[i] == A[j] == B[i] == B[j]
的情况下,字符串 A
与 B
相等。因此,如果 A == B
,我们应当检查每个索引 i
以寻找具有相同值的两个匹配。
在 A[i] == B[j], A[j] == B[i], (A[i] != A[j])
的情况下,其余索引是相匹配的。所以如果 A
和 B
只有两个不匹配的索引(记作 i
和 j
),我们应该检查并确保等式 A[i] == B[j]
和 A[j] == B[i]
成立。
复杂度分析
-
时间复杂度:,其中 是
A
和B
的长度。 -
空间复杂度:。