# C#LeetCode刷题之#389-找不同（Find the Difference）

s = “abcd”
t = “abcde”

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.

```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);

}

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 ' ';
}

}```

```a
x```

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