力扣-389 找不同

题目描述

给定两个字符串 s 和 t，它们只包含小写字母。字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。

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

示例

输入：s = “abcd”, t = “abcde”

输出：“e”

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

源代码

class Solution {
public:
    char findTheDifference(string s, string t) {
        if(s.length()==0) {
            return t[0];
        }
        //定义两个数组，分别表示字符串s,t中出现的字母和个数
        int arr1[26]={0},arr2[26]={0};
        for(int i=0;i<s.length();i++){
            arr1[s[i]-'a']++;
        }
        for(int i=0;i<t.length();i++){
            arr2[t[i]-'a']++;
        }
        for(int i=0;i<26;i++){
            if(arr1[i]!=arr2[i])  //如果s中出现的字母个数和t中不相等
            {
                return 'a'+i;
            }
        }
        return ";
    }
};
           

复杂度分析：

• 时间复杂度：O(N)，其中 N为字符串的长度。
• 空间复杂度：O(∣Σ∣)，其中 Σ 是字符集，这道题中字符串只包含小写字母，∣Σ∣=26。需要使用数组对每个字符计数。