leetcode 859. 亲密字符串

leetcode 859. 亲密字符串

题目描述

859. 亲密字符串

给你两个字符串 s 和 goal ，只要我们可以通过交换 s 中的两个字母得到与 goal 相等的结果，就返回 true ；否则返回 false 。

交换字母的定义是：取两个下标 i 和 j （下标从 0 开始）且满足 i != j ，接着交换 s[i] 和 s[j] 处的字符。

例如，在 "abcd" 中交换下标 0 和下标 2 的元素可以生成 "cbad" 。

示例 1：

输入：s = "ab", goal = "ba" 输出：true 解释：你可以交换 s[0] = 'a' 和 s[1] = 'b' 生成 "ba"，此时 s 和 goal 相等。 示例 2：

输入：s = "ab", goal = "ab" 输出：false 解释：你只能交换 s[0] = 'a' 和 s[1] = 'b' 生成 "ba"，此时 s 和 goal 不相等。 示例 3：

输入：s = "aa", goal = "aa" 输出：true 解释：你可以交换 s[0] = 'a' 和 s[1] = 'a' 生成 "aa"，此时 s 和 goal 相等。

提示：

1 <= s.length, goal.length <= 2 * 104 s 和 goal 由小写英文字母组成

解题思路

法1

方法1:模拟\

1. 判断两个字符串长度是否相同

2. 记录s与g不同的字符的位置,模拟交换了位置(g[i]==s[j]&&g[z]==s[i]),

3. 如果满足并且后面没有其他不同的字符,就返回true,否则返回false

• 时间复杂度(O(n))
• 空间复杂度(O(1))

执行结果

法1

首先判断两个字符串的长度，如果不相等，则一定无法通过交换字母得到相等的结果，直接返回 false。

然后，如果两个字符串完全相等，我们需要判断是否存在重复字符。我们可以使用一个集合（使用 map[byte]bool 实现）来存储已经出现过的字符，如果发现有重复的字符，则返回 true。如果没有重复的字符，则返回 false。

最后，如果两个字符串不相等，我们需要找出它们之间不匹配的字符。我们使用一个数组 diff 来存储不匹配的字符的索引。如果 diff 的长度不等于 2，则说明有超过两个字符不匹配，返回 false。如果 diff 的长度等于 2，我们判断交换后的字符串是否与 goal 相等，即判断 s[diff[0]] == goal[diff[1]] && s[diff[1]] == goal[diff[0]]，如果成立，则返回 true，否则返回 false。

func buddyStrings(s string, goal string) bool {
    if len(s) != len(goal) {
        return false
    }
    
    if s == goal {
        // 如果两个字符串相等，判断是否存在重复字符
        set := make(map[byte]bool)
        for i := 0; i < len(s); i++ {
            if set[s[i]] {
                return true
            }
            set[s[i]] = true
        }
        return false
    }
    
    // 存储不匹配的字符索引
    var diff []int
    
    for i := 0; i < len(s); i++ {
        if s[i] != goal[i] {
            diff = append(diff, i)
        }
    }
    
    if len(diff) != 2 {
        return false
    }
    
    // 判断交换后的字符串是否与 goal 相等
    i, j := diff[0], diff[1]
    return s[i] == goal[j] && s[j] == goal[i]
}

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 0 ms , 在所有 Go 提交中击败了 100.00% 的用户 内存消耗： 2.2 MB , 在所有 Go 提交中击败了 89.29% 的用户 通过测试用例： 34 / 34 炫耀一下: