执行逐位运算使字符串相等

难度: Medium

给你两个下标从 0 开始的二元字符串 s 和 target ，两个字符串的长度均为 n 。你可以对 s 执行下述操作任意次：

选择两个不同的下标 i 和 j ，其中 0 <= i, j < n 。
同时，将 s[i] 替换为 (s[i] OR s[j]) ，s[j] 替换为 (s[i] XOR s[j]) 。

例如，如果 s = "0110" ，你可以选择 i = 0 和 j = 2，然后同时将 s[0] 替换为 (s[0] OR s[2] = 0 OR 1 = 1)，并将 s[2] 替换为 (s[0] XOR s[2] = 0 XOR 1 = 1)，最终得到 s = "1110" 。

如果可以使 s 等于 target ，返回 true ，否则，返回 false 。

示例 1：

输入：s = "1010", target = "0110"
输出：true
解释：可以执行下述操作：
- 选择 i = 2 和 j = 0 ，得到 s = "0010".
- 选择 i = 2 和 j = 1 ，得到 s = "0110".
可以使 s 等于 target ，返回 true 。

示例 2：

输入：s = "11", target = "00"
输出：false
解释：执行任意次操作都无法使 s 等于 target 。

提示：

n == s.length == target.length
2 <= n <= 10⁵
s 和 target 仅由数字 0 和 1 组成

Submission

运行时间: 29 ms

内存: 16.5 MB

class Solution:
    def makeStringsEqual(self, s: str, target: str) -> bool:
        return ('1' in s) == ('1' in target)

Explain

该题解的核心思路是利用位运算的特性来判断字符串 s 能否经过一系列操作后与 target 字符串相等。观察到，只要字符串 s 中存在至少一个 '1'，我们就可以通过位运算操作将任何位置的字符变为 '1' 或 '0'。如果 s 中没有 '1'，则 s 中的所有字符都是 '0'，无法通过任何操作变为 '1'。因此，只需检查 s 和 target 是否都至少包含一个 '1' 或者都不包含 '1'，即可判断它们是否能通过一系列操作变得相同。因此，解法仅需要检查两个字符串是否都包含 '1'或者都不包含 '1'即可。

时间复杂度: O(n)

空间复杂度: O(1)

# 定义一个函数来判断是否可以通过位运算使两个字符串相等
class Solution:
    def makeStringsEqual(self, s: str, target: str) -> bool:
        # 检查字符串 s 和 target 是否都包含字符 '1'
        # ('1' in s) 检查 s 中是否至少有一个 '1'
        # ('1' in target) 检查 target 中是否至少有一个 '1'
        # 如果两个字符串状态相同（都有 '1' 或都没有 '1'），返回 True，否则返回 False
        return ('1' in s) == ('1' in target)

Explore

在题解中，通过使用位运算的特性可以实现任意字符的转换。具体方法是：若s中至少有一个'1'，则可以选择一个为'1'的下标i和任意一个下标j。通过设置s[i]为(s[i] OR s[j])和s[j]为(s[i] XOR s[j])，可以实现以下转换：1. 如果想将s[j]变为'1'，则选择s[i]='1'，此时s[i] OR s[j]无论s[j]是什么，结果都是'1'；s[i] XOR s[j]会使s[j]变为'1'（当s[j]是'0'时）。2. 若想将s[j]变为'0'，则选择s[i]='1'和s[j]='1'，这样s[i] XOR s[j]结果为'0'。通过这些操作，可以将任何位置的字符转换为'1'或'0'，只要s中存在至少一个'1'。

在给定的题解逻辑中，如果s和target都不包含'1'，即都是全'0'的字符串，已经暗示了两个字符串在每个对应位置上的字符都是'0'。由于s和target的长度相同，且都不包含'1'，这表明两个字符串在每个位置上的字符都相同，都是'0'。因此，此种情况下不需要额外检查两个字符串是否完全相等，因为它们已经由于都是全'0'而相等。

在题解提供的逻辑中，没有必要考虑s和target中'1'的个数和位置是否相同。这是因为，只要s中存在至少一个'1'，利用题目允许的位运算，可以自由地将任何位置的字符转换为'0'或'1'。这意味着，无论target字符串是什么，只要它的长度与s相同，我们都可以通过调整将s转换成与target完全相同的字符串。因此，只需检查s中是否至少有一个'1'，如果有，就可以实现任何形式的target，无论'1'的个数和位置如何。