LeetCode 389. 找不同

Categories:

题目描述
思路分析
1. 解法一：异或抵消（推荐）
2. 解法二：计数统计
相似题目

题目描述

✅ 389. 找不同

思路分析

解法一：异或抵消（推荐）

核心思路：

将 s 与 t 的全部字符进行异或。

相同字符两两抵消，最终结果就是多出来的字符。

复杂度分析：

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

空间复杂度：O(1)。

class Solution {
    public char findTheDifference(String s, String t) {
        int xor = 0;

        for (int i = 0; i < s.length(); i++) {
            xor ^= s.charAt(i);
        }

        for (int i = 0; i < t.length(); i++) {
            xor ^= t.charAt(i);
        }

        return (char) xor;
    }
}

func findTheDifference(s string, t string) byte {
	xor := 0
	for i := 0; i < len(s); i++ {
		xor ^= int(s[i])
	}

	for i := 0; i < len(t); i++ {
		xor ^= int(t[i])
	}

	return byte(xor)
}

解法二：计数统计

核心思路：

统计 t 中字符出现次数，减去 s 中字符出现次数。

出现次数为 1 的字符即为答案。

复杂度分析：

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

空间复杂度：O(1)，字母表固定大小。

class Solution {
    public char findTheDifference(String s, String t) {
        int[] cnt = new int[26];

        for (int i = 0; i < t.length(); i++) {
            cnt[t.charAt(i) - 'a']++;
        }

        for (int i = 0; i < s.length(); i++) {
            cnt[s.charAt(i) - 'a']--;
        }

        for (int i = 0; i < 26; i++) {
            if (cnt[i] == 1) {
                return (char) ('a' + i);
            }
        }

        return ' ';
    }
}

func findTheDifference(s string, t string) byte {
	cnt := make([]int, 26)

	for i := 0; i < len(t); i++ {
		cnt[t[i]-'a']++
	}

	for i := 0; i < len(s); i++ {
		cnt[s[i]-'a']--
	}

	for i := 0; i < 26; i++ {
		if cnt[i] == 1 {
			return byte('a' + i)
		}
	}

	return ' '
}

相似题目

题目	难度	考察点
242. 有效的字母异位词	简单	计数
387. 字符串中的第一个唯一字符	简单	计数
268. 丢失的数字	简单	位运算
136. 只出现一次的数字	简单	位运算
409. 最长回文串	简单	计数

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/47584640