Medium

题目描述

如果你可以通过以下操作将一个字符串转换为另一个字符串，那么这两个字符串被认为是"接近"的：

操作1： 交换任意两个现有字符。

  • 例如：abcde -> aecdb

操作2： 将一个现有字符的所有出现转换为另一个现有字符，同时将另一个字符的所有出现转换为第一个字符。

  • 例如：aacabb -> bbcbaa（所有的a变成b，所有的b变成a）

你可以在任一字符串上使用这些操作任意次数。

给定两个字符串 word1 和 word2，如果 word1 和 word2 接近，返回 true，否则返回 false。

示例 1：

输入：word1 = "abc", word2 = "bca"
输出：true
解释：你可以通过2次操作将word1转换为word2。
应用操作1："abc" -> "acb"
应用操作1："acb" -> "bca"

示例 2：

输入：word1 = "a", word2 = "aa"
输出：false
解释：无法通过任何操作将word1转换为word2，反之亦然。

示例 3：

输入：word1 = "cabbba", word2 = "abbccc"
输出：true
解释：你可以通过3次操作将word1转换为word2。
应用操作1："cabbba" -> "caabbb"
应用操作2："caabbb" -> "baaccc"
应用操作2："baaccc" -> "abbccc"

提示：

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

解题思路

这道题的关键是理解两个操作的本质：

  1. 操作1（交换字符）：可以任意重排字符串，这意味着字符的顺序不重要，只要字符集合相同即可。

  2. 操作2（字符转换）：可以将一个字符的所有出现替换为另一个字符，前提是两个字符都在原字符串中存在。

基于这两个操作，两个字符串"接近"需要满足以下条件：

  1. 字符集合相同：两个字符串必须包含完全相同的字符类型。因为操作2只能在已存在的字符间转换，不能创造新字符。

  2. 频次分布相同：每个字符的出现次数可以通过操作2重新分配，所以只要两个字符串的字符频次排序后相同即可。

解题步骤：

  1. 统计两个字符串中每个字符的出现频次
  2. 检查两个字符串的字符集合是否相同
  3. 将两个字符串的频次数组排序后比较是否相同

时间复杂度主要来自于字符频次统计和排序操作。

代码实现

class Solution {
public:
    bool closeStrings(string word1, string word2) {
        if (word1.length() != word2.length()) return false;
        
        vector<int> freq1(26, 0), freq2(26, 0);
        
        // 统计字符频次
        for (char c : word1) {
            freq1[c - 'a']++;
        }
        for (char c : word2) {
            freq2[c - 'a']++;
        }
        
        // 检查字符集合是否相同
        for (int i = 0; i < 26; i++) {
            if ((freq1[i] == 0) != (freq2[i] == 0)) {
                return false;
            }
        }
        
        // 比较频次分布
        sort(freq1.begin(), freq1.end());
        sort(freq2.begin(), freq2.end());
        
        return freq1 == freq2;
    }
};

class Solution:
    def closeStrings(self, word1: str, word2: str) -> bool:
        if len(word1) != len(word2):
            return False
        
        from collections import Counter
        
        # 统计字符频次
        count1 = Counter(word1)
        count2 = Counter(word2)
        
        # 检查字符集合是否相同
        if set(count1.keys()) != set(count2.keys()):
            return False
        
        # 比较频次分布
        return sorted(count1.values()) == sorted(count2.values())

public class Solution {
    public bool CloseStrings(string word1, string word2) {
        if (word1.Length != word2.Length) return false;
        
        int[] freq1 = new int[26];
        int[] freq2 = new int[26];
        
        // 统计字符频次
        foreach (char c in word1) {
            freq1[c - 'a']++;
        }
        foreach (char c in word2) {
            freq2[c - 'a']++;
        }
        
        // 检查字符集合是否相同
        for (int i = 0; i < 26; i++) {
            if ((freq1[i] == 0) != (freq2[i] == 0)) {
                return false;
            }
        }
        
        // 比较频次分布
        Array.Sort(freq1);
        Array.Sort(freq2);
        
        return freq1.SequenceEqual(freq2);
    }
}

/**
 * @param {string} word1
 * @param {string} word2
 * @return {boolean}
 */
var closeStrings = function(word1, word2) {
    if (word1.length !== word2.length) return false;
    
    const freq1 = {};
    const freq2 = {};
    
    for (let char of word1) {
        freq1[char] = (freq1[char] || 0) + 1;
    }
    
    for (let char of word2) {
        freq2[char] = (freq2[char] || 0) + 1;
    }
    
    const chars1 = Object.keys(freq1).sort();
    const chars2 = Object.keys(freq2).sort();
    
    if (chars1.join('') !== chars2.join('')) return false;
    
    const counts1 = Object.values(freq1).sort((a, b) => a - b);
    const counts2 = Object.values(freq2).sort((a, b) => a - b);
    
    return counts1.join('') === counts2.join('');
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n + k log k)n为字符串长度，k为不同字符数量(最多26)，主要开销来自频次统计和排序
空间复杂度O(1)只使用固定大小的数组存储26个字母的频次

相关题目