2546. Apply Bitwise Operations to Make Strings Equal
Description
You are given two 0-indexed binary strings s
and target
of the same length n
. You can do the following operation on s
any number of times:
- Choose two different indices
i
andj
where0 <= i, j < n
. - Simultaneously, replace
s[i]
with (s[i]
ORs[j]
) ands[j]
with (s[i]
XORs[j]
).
For example, if s = "0110"
, you can choose i = 0
and j = 2
, then simultaneously replace s[0]
with (s[0]
OR s[2]
= 0
OR 1
= 1
), and s[2]
with (s[0]
XOR s[2]
= 0
XOR 1
= 1
), so we will have s = "1110"
.
Return true
if you can make the string s
equal to target
, or false
otherwise.
Example 1:
Input: s = "1010", target = "0110" Output: true Explanation: We can do the following operations: - Choose i = 2 and j = 0. We have now s = "0010". - Choose i = 2 and j = 1. We have now s = "0110". Since we can make s equal to target, we return true.
Example 2:
Input: s = "11", target = "00" Output: false Explanation: It is not possible to make s equal to target with any number of operations.
Constraints:
n == s.length == target.length
2 <= n <= 105
s
andtarget
consist of only the digits0
and1
.
Solutions
Solution 1: Lateral Thinking
We notice that $1$ is actually a "tool" for number conversion. Therefore, as long as both strings either have $1$ or neither have $1$, we can make the two strings equal through operations.
The time complexity is $O(n)$, where $n$ is the length of the string. The space complexity is $O(1)$.
1 2 3 |
|
1 2 3 4 5 |
|
1 2 3 4 5 6 7 8 |
|
1 2 3 |
|
1 2 3 |
|
1 2 3 4 5 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|