LeetCode——Find the Difference

Question

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.

Example:

Input:
s = "abcd"
t = "abcde"

Output:
e

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

Solution

用hash table求解，時間復雜度為O(2n)

用異或求解，這道題和single number?的問題是一個意思，兩個字符串中，找出那個單個的字符。時間復雜度為O(n)。

Answer

class Solution { public:char findTheDifference(string s, string t) {map<char, int> dict;for (char c : s)dict[c]++;map<char, int> dict2;for (char c : t) {dict2[c]++;if (dict2[c] > dict[c])return c;}} };

用異或求解。

class Solution { public:char findTheDifference(string s, string t) {char r=0;for(char c:s) r ^=c;for(char c:t) r ^=c;return r;} };

轉載于:https://www.cnblogs.com/zhonghuasong/p/6658700.html

總結

以上是生活随笔為你收集整理的LeetCode——Find the Difference的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。