389. Find the Difference
1. Description
You are given two strings s and t.
String t is generated by random shuffling string s and then add one more letter at a random position.
Return the letter that was added to t.
2. Example
Example 1:
Input: s = “abcd”, t = “abcde”
Output: “e”
Explanation: ‘e’ is the letter that was added.
Example 2:
Input: s = “”, t = “y”
Output: “y”
Example 3:
Input: s = “a”, t = “aa”
Output: “a”
Example 4:
Input: s = “ae”, t = “aea”
Output: “a”
3. Constraints
- 0 <= s.length <= 1000
- t.length == s.length + 1
- s and t consist of lower-case English letters.
4. Solutions
My Accepted Solution
n = i_originStr.size()
Time complexity: O(n)
Space complexity: O(1)
class Solution
{
public:
// char findTheDifference(string s, string t)
char findTheDifference(string &i_originStr, string &i_laterStr)
{
// as constraints say, s and t consist of lower-case English letters
vector<int> originStrLetters(26);
vector<int> laterStrLetters(26);
for(int i = 0; i < i_originStr.size(); i++)
originStrLetters[i_originStr[i] - 'a']++;
for(int i = 0; i < i_laterStr.size(); i++)
laterStrLetters[i_laterStr[i] - 'a']++;
for(int i = 0; i < 26; i++)
{
if(originStrLetters[i] != laterStrLetters[i])
return i + 'a';
}
return '@'; // for compile check
}
};
4.1 XOR
n = i_originStr.size()
Time complexity: O(n)
Space complexity: O(1)
class Solution
{
public:
// char findTheDifference(string s, string t)
char findTheDifference(string &i_originStr, string &i_laterStr)
{
char result = i_laterStr.front();
for(int i = 0; i < i_originStr.size(); i++)
result ^= i_originStr[i];
for(int i = 1; i < i_laterStr.size(); i++)
result ^= i_laterStr[i];
return result;
}
};