LeetCode 859. 亲密字符串

Categories:

题目描述
思路分析
1. 解法一：模拟交换（推荐）
相似题目

题目描述

✅ 859. 亲密字符串

思路分析

解法一：模拟交换（推荐）

核心思路：

若长度不同直接返回 false。

若字符串相等，必须存在至少一个重复字符，才能交换后仍相等。

否则记录所有不相等位置，必须正好两处且互换后相等。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字符串长度。

空间复杂度：O(1)。

class Solution {
    public boolean buddyStrings(String s, String goal) {
        if (s.length() != goal.length()) {
            return false;
        }

        if (s.equals(goal)) {
            int[] cnt = new int[26];
            for (char ch : s.toCharArray()) {
                cnt[ch - 'a']++;
                if (cnt[ch - 'a'] > 1) {
                    return true;
                }
            }
            return false;
        }

        int first = -1;
        int second = -1;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != goal.charAt(i)) {
                if (first == -1) {
                    first = i;
                } else if (second == -1) {
                    second = i;
                } else {
                    return false;
                }
            }
        }

        return second != -1
                && s.charAt(first) == goal.charAt(second)
                && s.charAt(second) == goal.charAt(first);
    }
}

func buddyStrings(s string, goal string) bool {
	if len(s) != len(goal) {
		return false
	}

	if s == goal {
		var cnt [26]int
		for i := 0; i < len(s); i++ {
			idx := s[i] - 'a'
			cnt[idx]++
			if cnt[idx] > 1 {
				return true
			}
		}
		return false
	}

	first := -1
	second := -1
	for i := 0; i < len(s); i++ {
		if s[i] != goal[i] {
			if first == -1 {
				first = i
			} else if second == -1 {
				second = i
			} else {
				return false
			}
		}
	}

	return second != -1 && s[first] == goal[second] && s[second] == goal[first]
}

相似题目

题目	难度	考察点
161. 相隔为 1 的编辑距离	中等	字符串比较
242. 有效的字母异位词	简单	计数
551. 学生出勤记录 I	简单	字符串
925. 长按键入	简单	双指针
345. 反转字符串中的元音字母	简单	双指针

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/54008582