问题

该文章的最新版本已迁移至个人博客【比特飞】，单击链接 https://www.byteflying.com/archives/4062 访问。

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

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

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

输入：

s = "abcd"

t = "abcde"

输出：

e

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

---

Given two strings s and t which consist of only lowercase letters.

String t is generated by random shuffling string s and then add one more letter at a random position.

Find the letter that was added in t.

Input:

s = "abcd"

t = "abcde"

Output:

e

Explanation:'e' is the letter that was added.

---

示例

该文章的最新版本已迁移至个人博客【比特飞】，单击链接 https://www.byteflying.com/archives/4062 访问。

public class Program {

    public static void Main(string[] args) {
        var s = "ecb";
        var t = "beca";

        var res = FindTheDifference(s, t);
        Console.WriteLine(res);

        s = "loveleetcode";
        t = "loveleetxcode";

        res = FindTheDifference2(s, t);
        Console.WriteLine(res);

        Console.ReadKey();
    }

    private static char FindTheDifference(string s, string t) {
        var cs = s.ToArray();
        Array.Sort(cs);
        var ct = t.ToArray();
        Array.Sort(ct);
        var i = 0;
        for(; i < cs.Length; i++) {
            if(cs[i] != ct[i]) return ct[i];
        }
        return ct[i];
    }

    private static char FindTheDifference2(string s, string t) {
        var dic = new Dictionary<char, int>();
        foreach(var c in s) {
            if(dic.ContainsKey(c)) {
                dic[c]++;
            } else {
                dic[c] = 1;
            }
        }
        foreach(var c in t) {
            if(dic.ContainsKey(c)) {
                dic[c]--;
                if(dic[c] < 0) return c;
            } else {
                return c;
            }
        }
        return ' ';
    }

}

以上给出2种算法实现，以下是这个案例的输出结果：

该文章的最新版本已迁移至个人博客【比特飞】，单击链接 https://www.byteflying.com/archives/4062 访问。

a
x

---

分析：

FindTheDifference 的时间复杂度基于排序所使用的排序算法,FindTheDifference2 的时间复杂度为：  。