Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit series activities – click on the task to see the details of the activities.

I. Problem description

I give you two strings s and T. You can append any character to s or t in a single operation.

Returns the minimum number of steps required to make s and T mutually alphabetic allographs.

An anagram is a string of the same letters but in a different (or identical) order.

Title link: The minimum number of steps to make two strings an alphabetic allotopic

Two, the title requirements

The sample

Input: s = "leetcode", t = "coats" Output: 7 Explanation: - Perform 2 steps to append "as" to S = "leetcodeAs". - Perform 5 steps to append "leede" to t = "coats" to get t = "coatsleede". "Leetcodeas" and "coatsleede" are alphabetic allographs. So 2 plus 5 is 7 steps. It can be shown that you cannot make these two strings alphabetic allographs of each other in less than seven steps.Copy the code

inspection

1. String application is easy to timeout. 2Copy the code

Third, problem analysis

So my initial idea is, I’m going to iterate over characters that are in string S and not in string T, I’m going to iterate over characters that are in string T and not in string S, and I’m going to print the result.

The repeated occurrences require special calculations, so I made s1 an intermediate variable;

But this method timeout, the remaining 20 tests can not pass, timeout to optimize the pain who knows.

The C++ template library map can count by counting the minimum number of identical characters in two strings and subtracting the total length of the two strings by 2.

Map <char,int>a,b; It is expressed as follows:

leetcode
c 1  d 1  e 3  l 1  o 1  t 1
coats
a 1  c 1  o 1  s 1  t 1  
Copy the code

If two strings have the same number of characters, select the smallest number of identical characters.

Four, coding implementation

class Solution {
public:
    int minSteps(string s, string t) {
        map<char.int>a,b;// Define two map arrays
        int i,m=s.size(),n=t.size(),ans=0;// Data initialization
        char j;
        for(i=0; i<m; i++) { a[s[i]]++;// Map counts the string s
        }
        for(i=0; i<n; i++) { b[t[i]]++;// Map counts the string t
        }
         for(j='a'; j <= 'z'; j++)// Note that the values m['a'] are initialized to 0 at the beginning
        {
            ans+= min(a[j], b[j]);// Get the minimum value of the same public character
        }
        return m+n2 -*ans;// Return the result}};Copy the code

V. Test results

It’s going to take a little bit longer to execute, but let me see what ELSE I can do.