Medium

题目描述

给你两个长度为 n 的 0 索引二进制字符串 s 和 target。你可以对 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^5
  • s 和 target 只包含数字 0 和 1

解题思路

这道题需要我们分析按位运算的特性来找到规律。

关键观察：

  1. 运算特性分析：对于操作 (s[i] OR s[j], s[i] XOR s[j])，我们来分析所有可能的情况：

    • (0,0) → (0,0)：保持不变
    • (0,1) → (1,1)：产生两个1
    • (1,0) → (1,1)：产生两个1
    • (1,1) → (1,0)：保持一个1，产生一个0

  2. 重要发现：

    • 当我们有至少一个1时，可以通过操作产生更多的1
    • 当我们有至少一个1和一个0时，可以通过 (1,1) → (1,0) 来减少1的数量
    • 但是，如果字符串全是0，我们无法产生任何1

  3. 核心规律：

    • 如果 s 全是0而 target 不全是0，或者 target 全是0而 s 不全是0，则不可能转换
    • 在其他所有情况下都可能转换成功

这是因为：只要两个字符串中都至少包含一个1，我们就可以通过操作来任意调整1的分布位置。

代码实现

class Solution {
public:
    bool makeStringsEqual(string s, string target) {
        bool hasOneInS = false, hasOneInTarget = false;
        
        for (char c : s) {
            if (c == '1') {
                hasOneInS = true;
                break;
            }
        }
        
        for (char c : target) {
            if (c == '1') {
                hasOneInTarget = true;
                break;
            }
        }
        
        return hasOneInS == hasOneInTarget;
    }
};

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

public class Solution {
    public bool MakeStringsEqual(string s, string target) {
        bool hasOneInS = s.Contains('1');
        bool hasOneInTarget = target.Contains('1');
        return hasOneInS == hasOneInTarget;
    }
}

/**
 * @param {string} s
 * @param {string} target
 * @return {boolean}
 */
var makeStringsEqual = function(s, target) {
    const hasOneInS = s.includes('1');
    const hasOneInTarget = target.includes('1');
    
    return hasOneInS === hasOneInTarget;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型时间复杂度空间复杂度
时间复杂度O(n)O(1)
空间复杂度O(1)O(1)

其中 n 是字符串的长度。我们只需要遍历字符串检查是否包含字符'1’，时间复杂度为 O(n)，不需要额外空间，空间复杂度为 O(1)。

相关题目