题目描述

给你两个下标从 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。

样例

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

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

限制

• n == s.length == target.length
• 2 <= n <= 10^5
• s 和 target 仅由数字 0 和 1 组成。

算法

(思维题) $O(n)$

1. 如果 $target$ 全是 $0$，则 $s$ 也必须全是 $0$，否则无法变成 $target$，这是因为在题意的规则下，$s$ 至少存在一个 $1$ 无法变成 $0$。
2. 如果 $target$ 不全是 $0$，但 $target$ 全是 $0$，也无法变成 $target$，因为全是 $0$ 的情况下无法出现 $1$。

时间复杂度

• 遍历数组一次，故时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    bool makeStringsEqual(string s, string target) {
        const int n = s.size();
        bool s0 = true, t0 = true;

        for (int i = 0; i < n; i++) {
            if (s[i] == '1') s0 = false;
            if (target[i] == '1') t0 = false;
        }

        return (s0 && t0) || (!s0 && !t0);
    }
};