给你两个下标从 0 开始的 二元 字符串 s
和 target
,两个字符串的长度均为 n
。你可以对 s
执行下述操作 任意 次:
- 选择两个 不同 的下标
i
和j
,其中0 <= i, j < n
。 - 同时,将
s[i]
替换为 (s[i]
ORs[j]
) ,s[j]
替换为 (s[i]
XORs[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 <= 105
s
和target
仅由数字0
和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);
}