Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.
I. Problem description
Given two strings s and t, they contain only lowercase letters.
The string t is randomly rearranged by the string S, and a letter is added at the random position.
Please find the letter added to t.
Find the difference.
Two, the title requirements
Sample 1
Input: s = "abcd", t = "abcde" Output: "e" Explanation: 'e' is the letter being added.Copy the code
The sample 2
Input: s = "", t = "y"Copy the code
inspection
1. Simple map application and bit calculation 2. 15 to 30 minutes is recommendedCopy the code
Third, problem analysis
In this article, you can read more details about bitwise operation.
Day 45: Bit operation
1.map
We can use the map function to count the number of occurrences of each character of the string S and t. If the number of occurrences of each character is different, we will find it.
You can sort it and compare it bit by bit.
2. Bit operations
How do characters relate to bit operations? If we concatenate two strings into one, the number of occurrences of the different string must be odd, since no one is pairing, so we can use the xOR operation of the bitwise operation.
Four, coding implementation
1.map
class Solution {
public:
char findTheDifference(string s, string t) {
int i;
map<char.int>a,b; // Map initializes two arrays
for(i=0; i<s.size(a); i++)// Iterate over the characters of the string s
a[s[i]]++;// Count the number
for(i=0; i<t.size(a); i++)// Iterate over the characters of the string t
b[t[i]]++;// Count the number
for(char j='a'; j<='z'; j++)// Only lowercase letters
{
if(a[j]! =b[j])/ / not the same
{
return j;/ / output}}return 0; }};Copy the code
2. Bit operations
class Solution {
public:
char findTheDifference(string s, string t) {
char ch=0;// Initialize variables
int i;
for(i=0; i<s.size(a); i++)// Xor the first character
{
ch=ch^s[i];
}
for(i=0; i<t.size(a); i++)// XOR the second character
{
ch=ch^t[i];
}
return ch;// Output the result}};Copy the code
V. Test results
Bit operation memory consumption is lower.