Question

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

English Version

题目描述

给你两个下标从 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 = "_0_0_1_0".
- 选择 i = 2 和 j = 1 ，得到 s = "0_11_0".
可以使 s 等于 target ，返回 true 。

示例 2：

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

 

提示：

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

解法

方法一：脑筋急转弯

我们注意到 $1$ 其实是数字转换的“工具”，因此只要两个字符串中都有 $1$ 或者都没有 $1$，那么就可以通过操作使得两个字符串相等。

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

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

class Solution {
  public boolean makeStringsEqual(String s, String target) {
    return s.contains("1") == target.contains("1");
  }
}

class Solution {
public:
  bool makeStringsEqual(string s, string target) {
    auto a = count(s.begin(), s.end(), '1') > 0;
    auto b = count(target.begin(), target.end(), '1') > 0;
    return a == b;
  }
};

func makeStringsEqual(s string, target string) bool {
  return strings.Contains(s, "1") == strings.Contains(target, "1")
}

function makeStringsEqual(s: string, target: string): boolean {
  return s.includes('1') === target.includes('1');
}

impl Solution {
  pub fn make_strings_equal(s: String, target: String) -> bool {
    s.contains('1') == target.contains('1')
  }
}

bool makeStringsEqual(char* s, char* target) {
  int count = 0;
  for (int i = 0; s[i]; i++) {
    if (s[i] == '1') {
      count++;
      break;
    }
  }
  for (int i = 0; target[i]; i++) {
    if (target[i] == '1') {
      count++;
      break;
    }
  }
  return !(count & 1);
}