Find the Difference

This wiki to show my solution for LeetCode problem Find the Difference

Solution steps:

• While string t is random shuffle from string s
• so if we sort both strings (s,t) it will be easily to find the different character
• loop from 0 to length of string s (while s is smaller than t)
• and compare if s[i] != t[i] then we found the difference character
• if loop ends then the final character of t is the different one
• Time Complexity: sort operation takes O(n log n) and another loop for comparison, so we have : O (n log n) + O (n log n) + O(n)
• while n = size of input string

Solution in C++:

char findTheDifference(string s, string t) {
	sort(s.begin(), s.end());
	sort(t.begin(), t.end());
	for (int i = 0; i < s.size(); i++)
	{
		if (s[i] != t[i]) return t[i];
	}
	return t[t.size() - 1];
}