LeetCode 389. 找不同

389. 找不同

题目：给定两个字符串 s 和 t ，它们只包含小写字母。
字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。
请找出在 t 中被添加的字母。
链接 https://leetcode.cn/problems/find-the-difference/

个人思路

1. 哈希表：统计这两个字符串出现的字符的次数，最后再循环添加有字符的字符串t的字典，当其某个字符出现次数不等于s的时候，就找出来被添加的字符

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        Map1 = {}
        Map2 = {}
        for i in s:
            Map1[i] = Map1.get(i,0) + 1
        for i in t:
            Map2[i] = Map2.get(i,0) + 1
        for i in Map2.keys():
            if Map1.get(i,0) != Map2.get(i,0):
                return i
        return '-1'
1
2
3
4
5
6
7
8
9
10
11
12

写得比官方的麻烦：
首先遍历字符串 s，对其中的每个字符都将计数值加 1；然后遍历字符串 t，对其中的每个字符都将计数值减 1。当发现某个字符计数值为负数时，说明该字符在字符串 t 中出现的次数大于在字符串 s 中出现的次数，因此该字符为被添加的字符。

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        Map = {}
        for i in s:
            Map[i] = Map.get(i,0) + 1
        for i in t:
            Map[i] = Map.get(i,-1) - 1
            if Map[i] < 0:
                return i
        return '-1'
1
2
3
4
5
6
7
8
9
10

官方思路

1. 求和
   将字符串 s 中每个字符的 ASCII 码的值求和，得到 A_s；对字符串 t 同样的方法得到 A_t。两者的差值 A_t-A_s即代表了被添加的字符。

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        a_s = sum([ord(i) for i in s])
        a_t = sum([ord(i) for i in t])
        return chr(a_t - a_s)
1
2
3
4
5

复杂度分析
时间复杂度：O(N)。
空间复杂度：O(1)。

2. 位运算
   如果将两个字符串拼接成一个字符串，则问题转换成求字符串中出现奇数次的字符。类似于「136. 只出现一次的数字」，我们使用位运算的技巧解决本题。
   不太了解位运算，这里贴个java的

class Solution {
    public char findTheDifference(String s, String t) {
        int ret = 0;
        for (int i = 0; i < s.length(); ++i) {
            ret ^= s.charAt(i);
        }
        for (int i = 0; i < t.length(); ++i) {
            ret ^= t.charAt(i);
        }
        return (char) ret;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/find-the-difference/solution/zhao-bu-tong-by-leetcode-solution-mtqf/

复杂度分析
时间复杂度：O(N)。
空间复杂度：O(1)。

建议查看一下链接了解其他方法:
https://leetcode.cn/problems/find-the-difference/solution/yi-ju-hua-zhao-bu-tong-reduce-gao-qi-lai-eqok/