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

题目

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

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

题解

【仅执行一次字符串交换能否使两个字符串相等】简单统计模拟

模拟

结果为 true 有两个充分条件：

s1 与 s2 完全相同
s1 与 s2 有两处不同，且不同处对应位置字符相同，即假设 \(i, j\) 两处位置不同，那么要求 \(s1[i] == s2[j] && s1[j] == s2[i]\)

以上两点满足其一即可

# Code language: Python
class Solution:
    def areAlmostEqual(self, s1: str, s2: str) -> bool:
        idx = -1
        for i, a, b in zip(count(0), s1, s2):
            if a == b:
                continue
            elif idx == -1:
                idx = i
            elif idx == -2:
                return False
            else:
                if a != s2[idx] or b != s1[idx]:
                    return False
                idx = -2
        return idx < 0

// Code language: Java
class Solution {
    public boolean areAlmostEqual(String s1, String s2) {
        int idx = -1;
        for (int i = 0, n = s1.length(); i < n; ++i) {
            char a = s1.charAt(i), b = s2.charAt(i);
            if (a == b) continue;               // 相同不用管
            else if (idx == -1) idx = i;        // 第一处不同记录下
            else if (idx == -2) return false;   // 超过两处不同
            else {
                if (a != s2.charAt(idx) || b != s1.charAt(idx))
                    return false;               // 不同的位置对应字符不同
                idx = -2;                       // 标记已有两处不同
            }
        }
        return idx < 0;
    }
}

// Code language: C++
class Solution {
public:
    bool areAlmostEqual(string s1, string s2) {
        int idx = -1;
        for (int i = 0, n = s1.size(); i < n; ++i) {
            if (s1[i] == s2[i]) continue;       // 相同不用管
            else if (idx == -1) idx = i;        // 第一处不同记录下
            else if (idx == -2) return false;   // 超过两处不同
            else {
                if (s1[i] != s2[idx] || s2[i] != s1[idx])
                    return false;               // 不同的位置对应字符不同
                idx = -2;                       // 标记已有两处不同
            }
        }
        return idx < 0;
    }
};

/* Code language: JavaScript */
/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var areAlmostEqual = function(s1, s2) {
    let idx = -1;
    for (let i = 0, n = s1.length; i < n; ++i) {
        const a = s1[i], b = s2[i];
        if (a == b) continue;               // 相同不用管
        else if (idx == -1) idx = i;        // 第一处不同记录下
        else if (idx == -2) return false;   // 超过两处不同
        else {
            if (a != s2[idx] || b != s1[idx])
                return false;               // 不同的位置对应字符不同
            idx = -2;                       // 标记已有两处不同
        }
    }
    return idx < 0;
};

/* Code language: Go */
func areAlmostEqual(s1 string, s2 string) bool {
    var idx, n = -1, len(s1)
    for i := 0; i < n; i++ {
        if s1[i] == s2[i] {
            continue
        } else if idx == -1 {
            idx = i
        } else if idx == -2 {
            return false
        } else {
            if s1[i] != s2[idx] || s2[i] != s1[idx] {
                return false
            }
            idx = -2
        }
    }
    return idx < 0
}

时间复杂度: \(O(n)\)
空间复杂度: \(O(1)\)

如果对你有帮助的话，请给我点个赞吧~

欢迎前往我的博客或 Algorithm - Github 查看更多题解

小鲸鱼的梦境

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

题目

标签

题解

模拟