Isomorphe Strings (Mustergleichheit)

1 Lösung

#341

Fortgeschrittener - C++ von JKooP - 06.03.2021 um 17:43 Uhr

Als isomorph bezeichnet man zwei oder mehrere Strings (Texte),
die zwar inhaltlich unterschiedlich sind, aber dennoch das gleiche Muster aufweisen.

Achtung:
Gleiche Buchstaben bedeuten Musterwiederholung! ABAB ist nicht ABCD, aber CDCD.

Beispiele:
s1 = ABBA; s2 = OTTO => true
s1 = PAPER; s2 = TITLE => true
s1 = EGG; s2 = ADD => true
s1 = BADC; s2 = BABA => false
s1 = BBBAAABA; s2 = AAABBBBA => false

Erstelle eine Funktion/Methode, die zwei Strings (Texte) hinsichtlich Isomorphie vergleicht.

Viel Spaß

Bitte melden Sie sich an um zur Aufgabenbeschreibung eine Frage zu stellen.

Frage stellen

Bitte melden Sie sich an um eine Lösung einzureichen.

Lösung einreichen

von JKooP (18090 Punkte) - 14.04.2021 um 17:53 Uhr

C++ 17

C-Code

#include <iostream>
#include <string>
#include <vector>
#include <tuple>
using namespace std;

bool is_isomorphic(string, string);

int main()
{
    vector<tuple<string, string>> v = { {"ABBA", "OTTO"}, {"PAPER", "TITLE"}, {"EGG", "ADD"}, {"BADC", "BABA"}, {"BBBAAABA", "AAABBBBA"} };
    for (const auto& i : v)
        cout << "{" << get<0>(i) << ", " << get<1>(i) << "} => " << (is_isomorphic(get<0>(i), get<1>(i)) == 1 ? "Wahr" : "Falsch") << endl;
}

bool is_isomorphic(string s, string t)
{
    if (s.length() != t.length())
        return false;

    char cS[256]{ 0 };
    char cT[256]{ 0 };

    for (size_t i = 0; i < s.length(); i++)
    {
        if (cS[s[i]] != cT[t[i]])
            return false;
        cS[s[i]] = cT[t[i]] = (char)i;
    }

    return true;
}