Geek asks and answers

Find the maximum number of characters that both lines have

Find the maximum number of characters that both lines have. Characters are case sensitive, that is, lowercase and uppercase characters are considered different.

Here is my code:

#include <iostream>
#include <cstring> 
using namespace std;

int main() {
    std::string a, b;
    int number_cases = 0, count = 0;
    cin >> number_cases;
    while (number_cases != 0) {
        cin >> a;
        cin >> b;
        for (int i = 0; i < a.size(); i++) {
            for (int j = 0; j < b.size(); j++) {
                if (a[i] == b[j]) {
                    count++;
                    b[j] = '#';
                    break;
                }
            }
        }
        cout << count << endl;
        count = 0;
        --number_cases;
    }
}

but it takes more than 1 second to start, I need to get it in less than 1 second or exactly 1 second. Any optimization tips?

+3
source share
4 answers

Just sort them and use set_intersection

#include <algorithm>
#include <iostream>
#include <iterator>
#include <string>

int main()
{
    std::string s1 = "Hello";
    std::string s2 = "World";

    std::sort(begin(s1), end(s1));
    std::sort(begin(s2), end(s2));

    std::string s3;
    std::set_intersection(begin(s1), end(s1), begin(s2), end(s2), std::back_inserter(s3));
    std::cout << s3.size() << ":" << s3;
}

Live example .

Note : if you are interested in unique overlapping characters, you can run std::uniqueon s3.

+2
source

, 256 . int[]arrayA A int [] arrayB B.

, int[] arrayA , arrayB 0 255, :

result +=Min(arrayA[i],arrayB[i]);

O (n + m + 256) = O (n) n, m - A B

0

, "", , , , bool:

bool inA[256] = {};
for ( auto current = a.begin(), end = a.end(); current != end; ++ current ) {
    inA[static_cast<unsigned char>(*current)] = true;
}
bool inB[256] = {};
for ( auto current = b.begin(), end = b.end(); current != end; ++ current ) {
    inB[static_cast<unsigned char>(*current)] = true;
}
int count = 0;
for (int i = 0; i != 256; ++ i ) {
    if ( inA[i] && inB[i] ) {
        ++ count;
    }
}

, , - , , . , .

0

:

std::size_t count_letter_in_common_with_dup(const std::string& s1, const std::string& s2)
{
    std::size_t present1[256] = {};
    std::size_t present2[256] = {};

    for (unsigned char c : s1) {
        ++present1[c];
    }
    for (unsigned char c : s2) {
        ++present2[c];
    }
    std::size_t res = 0;
    for (int i = 0; i != 256; ++i) {
        res += std::min(present1[i], present2[i]);
    }
    return res;
}
0

More articles:


All Articles