LeetCode_字符串_中等_1657.确定两个字符串是否接近

た入场券 2023-10-13 03:48 11阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

如果可以使用以下操作从一个字符串得到另一个字符串，则认为两个字符串接近：  
操作 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”

**示例 4：**  
输入：word1 = “cabbba”, word2 = “aabbss”  
输出：false  
解释：不管执行多少次操作，都无法从 word1 得到 word2 ，反之亦然。

**提示：**  
1 <= word1.length, word2.length <= 105  
word1 和 word2 仅包含小写英文字母

## 2.思路 ##

（1）等价转换  
分析题目可知，我们可以通过以下三个条件来确定两个字符串是否接近：

*  word1 和 word2 的长度必须相等；
 *  word1 和 word2 的字符种类相同；
 *  word1 和 word2 的字符频次相同；

## 3.代码实现（Java） ##

//思路1————等价转换
    class Solution {
        
        public boolean closeStrings(String word1, String word2) {
        
            int len1 = word1.length();
            int len2 = word2.length();
            //验证长度是否相同
            if (len1 != len2) {
        
                return false;
            }
            if (word1.equals(word2)) {
        
                return true;
            }
            //分别记录 word1 和 word2 中小写字母出现的次数
            int[] cnt1 = new int[26];
            int[] cnt2 = new int[26];
            for (int i = 0; i < len1; i++) {
        
                int index1 = word1.charAt(i) - 'a';
                cnt1[index1]++;
                int index = word2.charAt(i) - 'a';
                cnt2[index]++;
            }
            //验证字符种类是否相同
            for (int i = 0; i < cnt1.length; i++) {
        
                if ((cnt1[i] != 0 && cnt2[i] == 0) || (cnt1[i] == 0 && cnt2[i] != 0)) {
        
                    return false;
                }
            }
            //验证字符频次是否相同
            Arrays.sort(cnt1);
            Arrays.sort(cnt2);
            for (int i = 0; i < cnt1.length; i++) {
        
                if (cnt1[i] != cnt2[i]) {
        
                    return false;
                }
            }
            return true;
        }
    }