当前位置：首页 > article >正文

算法----确定两个字符串是否接近

article 2024/11/16 19:34:26

题目

如果可以使用以下操作从一个字符串得到另一个字符串，则认为两个字符串接近：

操作 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 仅包含小写英文字母

解决思路

首先，保证两个字符串都有对方的字符。
其次，重复字符的个数一致就可以

解决方法

    fun closeStrings2(word1: String, word2: String): Boolean {
        val countArray1 = IntArray(26) { 0 }
        val countArray2 = IntArray(26) { 0 }

        word1.forEach {
            val key = it - 'a'
            countArray1[key] = countArray1[key] + 1
        }
        word2.forEach {
            val key = it - 'a'
            countArray2[key] = countArray2[key] + 1
        }

        for (i in 0 until 26) {
            if (countArray1[i] + countArray2[i] == 0) {
                continue
            }
            if (countArray1[i] == 0 || countArray2[i] == 0) {
                return false
            }
        }
        Arrays.sort(countArray1)
        Arrays.sort(countArray2)
        return countArray1.contentEquals(countArray2)

    }