Как преобразовать одну строку в другую путем последовательной замены символов?

Question

В настоящее время я пытаюсь разработать алгоритм, который делает такие вещи:

Я получил две строки A и B, которые состоят из строчных букв 'a' - 'z', и я могу изменить строку A, используя следующие операции:

1. Select two characters 'c1' and 'c2' from the character set ['a'-'z'].
2. Replace all characters 'c1' in string A with character 'c2'.

Мне нужно найти минимальное количество операций, необходимых для преобразования строки A в строку B, когда это возможно.

У меня есть 2 идеи, которые не сработали

1. Simple range-based for cycle that changes string B and compares it with A.
2. Idea with map<char, int> that does the same.

Прямо сейчас я застрял на модульном тестировании в такой ситуации: «ab» переносится в «ba» за 3 итерации, а «ab c» в «bca» в 4 итерации. Мой алгоритм неверен, и мне нужны свободные идеи или рабочее решение. Кто-нибудь может помочь с этим?

Вот некоторый код, который показывает минимальный RepEx:

int Transform(string& A, string& B)
{
    int count = 0;

    if(A.size() != B.size()){
        return -1;
    }

    for(int i = A.size() - 1; i >= 0; i--){
        if(A[i]!=B[i]){
           char rep_elem = A[i];
           ++count;
           replace(A.begin(),A.end(),rep_elem,B[i]);
        }
    }

    if(A != B){
        return -1;
    }

    return count;
}

Как я могу улучшить это, или я должен найти другие идеи?

Answer 1

Прежде всего, не беспокойтесь о строковых операциях. Ваша проблема - алгоритмическая c, а не текстовая. Вы должны каким-то образом проанализировать свои данные и только потом распечатать свое решение.

Начните с построения структуры данных, которая сообщает для каждой буквы, какую букву следует заменить. Используйте массив (или std::map<char, char> - концептуально он должен быть похожим, но иметь другой синтаксис).

Если вы обнаружите, что нужно преобразовать букву в две разные буквы - ошибка, преобразование невозможно. В противном случае посчитайте количество нетривиальных циклов в графе конверсии.

Длина вашего решения будет количеством букв, которые не должны заменяться собой, плюс количество циклов.

Я думаю, что код для реализации этого будет слишком длинным, чтобы быть полезным.