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.
Examples:
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"Solution in Python:
To solve the problem of finding the letter that was added to string t after shuffling string s and adding one additional character, we can utilize a few different approaches. One efficient way to solve this is by using the XOR bitwise operation.
The XOR operation has an interesting property: any number XORed with itself results in 0, and any number XORed with 0 remains unchanged. By applying XOR across all characters in both strings, the characters that are present in both strings will cancel out, leaving us with the extra character in t.
class Solution:
def findTheDifference(self, s: str, t: str) -> str:
# Initialize the result with 0
result = 0
# XOR all characters in s
for char in s:
result ^= ord(char)
# XOR all characters in t
for char in t:
result ^= ord(char)
# The result now contains the ASCII value of the extra character
return chr(result)
# Example usage:
solution = Solution()
# Example 1
s1 = "abcd"
t1 = "abcde"
print(solution.findTheDifference(s1, t1)) # Output: "e"
# Example 2
s2 = ""
t2 = "y"
print(solution.findTheDifference(s2, t2)) # Output: "y"Explanation of the Code:
- Line 3: Define the
Solutionclass with thefindTheDifferencemethod. - Line 4: Initialize the
resultvariable with 0. This will hold the cumulative XOR result. - Lines 7-9: Iterate through each character in
s, convert the character to its ASCII value usingord(), and XOR it with theresult. - Lines 12-14: Iterate through each character in
t, convert the character to its ASCII value usingord(), and XOR it with theresult. - Line 17: Convert the final
resultback to a character usingchr()and return it. - Lines 20-28: Provide example usage to demonstrate the function with given examples.
This approach is efficient with a time complexity of O(n), where n is the length of the longer string (t). The space complexity is O(1) since we only use a few extra variables regardless of the input size.
Solution in Javascript:
/**
* @param {string} s
* @param {string} t
* @return {character}
*/
var findTheDifference = function(s, t) {
// Initialize the result with 0
let result = 0;
// XOR all characters in s
for (let i = 0; i < s.length; i++) {
result ^= s.charCodeAt(i);
}
// XOR all characters in t
for (let i = 0; i < t.length; i++) {
result ^= t.charCodeAt(i);
}
// The result now contains the ASCII value of the extra character
return String.fromCharCode(result);
};
// Example usage:
// Example 1
let s1 = "abcd";
let t1 = "abcde";
console.log(findTheDifference(s1, t1)); // Output: "e"
// Example 2
let s2 = "";
let t2 = "y";
console.log(findTheDifference(s2, t2)); // Output: "y"Solution in Java:
class Solution {
public char findTheDifference(String s, String t) {
// Initialize the result with 0
int result = 0;
// XOR all characters in s
for (int i = 0; i < s.length(); i++) {
result ^= s.charAt(i);
}
// XOR all characters in t
for (int i = 0; i < t.length(); i++) {
result ^= t.charAt(i);
}
// The result now contains the ASCII value of the extra character
return (char) result;
}
public static void main(String[] args) {
Solution solution = new Solution();
// Example 1
String s1 = "abcd";
String t1 = "abcde";
System.out.println(solution.findTheDifference(s1, t1)); // Output: 'e'
// Example 2
String s2 = "";
String t2 = "y";
System.out.println(solution.findTheDifference(s2, t2)); // Output: 'y'
}
}Solution in C#:
public class Solution {
public char FindTheDifference(string s, string t) {
// Initialize the result with 0
int result = 0;
// XOR all characters in s
foreach (char c in s) {
result ^= c;
}
// XOR all characters in t
foreach (char c in t) {
result ^= c;
}
// The result now contains the ASCII value of the extra character
return (char)result;
}
}