Нахождение количества общих символов во всех входных строках - C ++ 14 - PullRequest
0 голосов
/ 04 февраля 2019

Я пытался реализовать код для конкурса, который бы определял количество общих символов во всех входных строках.

Я пропустил формат ввода, но ограничение по времени составило 0,5 с, и поэтому я попыталсянапишите оптимальный код.Подход, который я придерживался, заключался в том, чтобы при вводе я помечал строку с минимальной длиной, чтобы ее можно было пройти позже.Затем я перебираю эту строку для извлечения каждого символа и проверяю, присутствует ли он во всех строках.Как только я проверяю наличие символа, я удаляю его из всех строк, чтобы сэкономить время.

#include<iostream>
#include<bits/stdc++.h>
#include<string>
using namespace std;
string s[205];
int t,len=0,n,k,count1,count2;
char a;
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        len=0;
        count1=0;
        count2=0;
        k=0;
        for(int i=0;i<n;++i)
        {
            cin>>s[i];
            if(i==0)
            {
                len = s[i].length();
            }
            else
            {
                if(s[i].length()<len)
                {
                    len = s[i].length(); //Finding string with min length
                    k = i;
                }
            }
        }
        for(int i=0;i<s[k].length();++i)
        {
            count1 = 0;
            a = s[k][i];
            for(int j=0;j<n;++j)
            {
                auto found = s[j].find(a);
                if(found==std::string::npos) //checking each character in all strings
                    break;
                else
                    count1++;
            }
            if(count1==n) //If char is in all strings
            {
                count2++;
            }
            for(int j=0;j<n;++j)
            {
                if(s[j].find(a)!=std::string::npos)
                {
                    s[j].erase(std::remove(s[j].begin(), s[j].end(), a), s[j].end()); //removing checked character from all strings
                }
            }

        }
        cout<<count2<<"\n"; //number of common characters

    }
    return 0;
}

Код выполнялся для нескольких тестовых случаев, но для большинства из них не удался.Пожалуйста, дайте мне знать, если в коде есть логический недостаток.

1 Ответ

0 голосов
/ 04 февраля 2019

Я рекомендую другой подход.Сначала создайте карту для каждой строки.Подсчитайте количество каждого персонажа.Подведите итоги всех минимумов.

Например:

s1 = "abcaa" => map1 = {'a': 3, 'b': 1, 'c': 1}, s2 = "ababc" =>map2 = {'a': 2, 'b': 2, 'c': 1}

=> 2 + 1 + 1 общих символов.

Вместо карты вы можете использоватьмассив, поскольку вы можете преобразовать символ в целое число.

Вместо карты вы можете использовать набор, если вы не хотите считать дубликаты.

s1 = "abcaad" =>map1 = {'a', 'b', 'c', 'd'}, s2 = "ababce" => map2 = {'a', 'b', 'c', 'e'}

С помощью std :: set_intersect вы можете определить общие символы.

#include <algorithm>
#include <iostream>
#include <set>
#include <string>

int main() {
    unsigned int t;
    std::cin >> t;
    while (t--) {
        unsigned int n;
        std::cin >> n;
        std::string temp;
        std::cin >> temp;
        std::set<char> intersect(temp.begin(), temp.end());
        while (--n) {
            std::cin >> temp;
            std::set<char> tempSet(temp.begin(), temp.end());
            std::set<char> newSet;
            std::set_intersection(tempSet.begin(), tempSet.end(), intersect.begin(), intersect.end(), std::inserter(newSet, newSet.begin()));
            intersect = newSet;
        }
        for (const auto c : intersect) {
            std::cout << c;
        }
        std::cout << std::endl;
    }
    return 0;
}
...