Medium

题目描述

给你两个下标从 0 开始的字符串 word1 和 word2。

一次 移动 由以下步骤组成：选择两个下标 i 和 j，分别满足 0 <= i < word1.length 和 0 <= j < word2.length，并交换 word1[i] 和 word2[j]。

如果可以通过 恰好一次移动，使 word1 和 word2 中不同字符的数目相等，则返回 true；否则，返回 false。

示例 1：

输入：word1 = "ac", word2 = "b"
输出：false
解释：交换任何一对字符都会导致第一个字符串有 2 个不同字符，而第二个字符串只有 1 个不同字符。

示例 2：

输入：word1 = "abcc", word2 = "aab"
输出：true
解释：我们将第一个字符串的下标 2 与第二个字符串的下标 0 交换。交换后得到 word1 = "abac" 和 word2 = "cab"，两者都有 3 个不同字符。

示例 3：

输入：word1 = "abcde", word2 = "fghij"
输出：true
解释：无论我们交换哪一对下标，两个结果字符串都将有 5 个不同字符。

提示：

  • 1 <= word1.length, word2.length <= 10^5
  • word1 和 word2 只包含小写英文字母

解题思路

这道题需要判断是否能通过恰好一次字符交换，使两个字符串的不同字符数量相等。

核心思路：

  1. 首先统计两个字符串中每个字符的出现频次
  2. 由于只有26个小写字母，我们可以枚举所有可能的交换组合（26×26=676种）
  3. 对于每种可能的交换（字符c1从word1交换到word2，字符c2从word2交换到word1），模拟交换过程并计算交换后两个字符串的不同字符数量

具体步骤：

  • 使用频次数组记录每个字符串中各字符的出现次数
  • 遍历所有可能的字符对(c1, c2)，其中c1来自word1，c2来自word2
  • 对于每个字符对，检查是否满足交换条件（word1中必须有c1，word2中必须有c2）
  • 模拟交换后计算新的不同字符数量，如果相等则返回true

时间复杂度优化： 由于字符集固定为26个字母，枚举所有组合的时间复杂度是常数级别的，整体算法效率很高。

代码实现

class Solution {
public:
    bool isItPossible(string word1, string word2) {
        vector<int> count1(26, 0), count2(26, 0);
        
        // 统计字符频次
        for (char c : word1) count1[c - 'a']++;
        for (char c : word2) count2[c - 'a']++;
        
        // 枚举所有可能的字符交换
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < 26; j++) {
                // 检查是否可以进行交换
                if (count1[i] == 0 || count2[j] == 0) continue;
                
                // 模拟交换
                count1[i]--; count1[j]++;
                count2[j]--; count2[i]++;
                
                // 计算交换后的不同字符数量
                int distinct1 = 0, distinct2 = 0;
                for (int k = 0; k < 26; k++) {
                    if (count1[k] > 0) distinct1++;
                    if (count2[k] > 0) distinct2++;
                }
                
                if (distinct1 == distinct2) return true;
                
                // 恢复原状态
                count1[i]++; count1[j]--;
                count2[j]++; count2[i]--;
            }
        }
        
        return false;
    }
};

class Solution:
    def isItPossible(self, word1: str, word2: str) -> bool:
        from collections import Counter
        
        count1 = Counter(word1)
        count2 = Counter(word2)
        
        # 枚举所有可能的字符交换
        for c1 in 'abcdefghijklmnopqrstuvwxyz':
            for c2 in 'abcdefghijklmnopqrstuvwxyz':
                # 检查是否可以进行交换
                if count1[c1] == 0 or count2[c2] == 0:
                    continue
                
                # 模拟交换
                count1[c1] -= 1
                count1[c2] += 1
                count2[c2] -= 1
                count2[c1] += 1
                
                # 计算交换后的不同字符数量
                distinct1 = sum(1 for v in count1.values() if v > 0)
                distinct2 = sum(1 for v in count2.values() if v > 0)
                
                if distinct1 == distinct2:
                    return True
                
                # 恢复原状态
                count1[c1] += 1
                count1[c2] -= 1
                count2[c2] += 1
                count2[c1] -= 1
        
        return False

public class Solution {
    public bool IsItPossible(string word1, string word2) {
        int[] count1 = new int[26];
        int[] count2 = new int[26];
        
        // 统计字符频次
        foreach (char c in word1) count1[c - 'a']++;
        foreach (char c in word2) count2[c - 'a']++;
        
        // 枚举所有可能的字符交换
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < 26; j++) {
                // 检查是否可以进行交换
                if (count1[i] == 0 || count2[j] == 0) continue;
                
                // 模拟交换
                count1[i]--; count1[j]++;
                count2[j]--; count2[i]++;
                
                // 计算交换后的不同字符数量
                int distinct1 = 0, distinct2 = 0;
                for (int k = 0; k < 26; k++) {
                    if (count1[k] > 0) distinct1++;
                    if (count2[k] > 0) distinct2++;
                }
                
                if (distinct1 == distinct2) return true;
                
                // 恢复原状态
                count1[i]++; count1[j]--;
                count2[j]++; count2[i]--;
            }
        }
        
        return false;
    }
}

var isItPossible = function(word1, word2) {
    const count1 = new Map();
    const count2 = new Map();
    
    for (let c of word1) {
        count1.set(c, (count1.get(c) || 0) + 1);
    }
    
    for (let c of word2) {
        count2.set(c, (count2.get(c) || 0) + 1);
    }
    
    for (let c1 of count1.keys()) {
        for (let c2 of count2.keys()) {
            let newCount1 = new Map(count1);
            let newCount2 = new Map(count2);
            
            newCount1.set(c1, newCount1.get(c1) - 1);
            if (newCount1.get(c1) === 0) {
                newCount1.delete(c1);
            }
            newCount1.set(c2, (newCount1.get(c2) || 0) + 1);
            
            newCount2.set(c2, newCount2.get(c2) - 1);
            if (newCount2.get(c2) === 0) {
                newCount2.delete(c2);
            }
            newCount2.set(c1, (newCount2.get(c1) || 0) + 1);
            
            if (newCount1.size === newCount2.size) {
                return true;
            }
        }
    }
    
    return false;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大O表示法说明
时间复杂度O(n + m)n和m分别是word1和word2的长度，字符统计需要O(n+m)，枚举26×26种组合为常数时间
空间复杂度O(1)只使用了固定大小的数组存储26个字母的频次

相关题目