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.