Go Java算法之找不同示例详解

找不同

给定两个字符串 s 和 t ，它们只包含小写字母。

字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。

请找出在 t 中被添加的字母。

• 示例 1：

输入：s = "abcd", t = "abcde"

输出："e"

解释：'e' 是那个被添加的字母。

• 示例 2：

输入：s = "", t = "y"

输出："y"  

提示：

0 <= s.length <= 1000

t.length == s.length + 1

• s 和 t 只包含小写字母

方法一：计数（Java）

首先遍历字符串 s，对其中的每个字符都将计数值加 1；然后遍历字符串 t，对其中的每个字符都将计数值减 1。

当发现某个字符计数值为负数时，说明该字符在字符串 t 中出现的次数大于在字符串 s 中出现的次数，因此该字符为被添加的字符。

class Solution {
   public char findTheDifference(String s, String t) {
       int[] cnt = new int[26];
       for (int i = 0; i < s.length(); ++i) {
           char ch = s.charAt(i);
           cnt[ch - 'a']++;
       }
       for (int i = 0; i < t.length(); ++i) {
           char ch = t.charAt(i);
           cnt[ch - 'a']--;
           if (cnt[ch - 'a'] < 0) {
               return ch;
           }
       }
       return ' ';
   }
}

N :字符串的长度

&Sigma; :字符集

时间复杂度：O(N)

空间复杂度：O(∣&Sigma;∣)

方法二：求和（Go）

本方法主要是利用了ASCII码，按照字符的ASCII码进行查找不同的字符。一次遍历计算出两个字符串的ASCII总和，根据差值既可以得出插入的字符

将字符串 s 中每个字符的 ASCII 码的值求和，得到 A_s

对字符串 t 同样的方法得到 A_t

两者的差值 A_t-A_s即代表了被添加的字符。

func findTheDifference(s, t string) byte {
   sum := 0
   for _, ch := range s {
       sum -= int(ch)
   }
   for _, ch := range t {
       sum += int(ch)
   }
   return byte(sum)
}

时间复杂度：O(N)

空间复杂度：O(1)

来源：https://juejin.cn/post/7135454951706705957