0

I'm currently trying to design an algorithm that doing such thing:

I got two strings A and B which consist of lowercase characters 'a'-'z' and I can modify string A using the following operations:

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

I need to find the minimum number of operations needed to convert string A to string B when possible.

I have 2 ideas that didn't work

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.

Right now I'm stuck on unit-testing with such situation : 'ab' is transferable to 'ba' in 3 iterations and 'abc' to 'bca' in 4 iterations. My algorithm is wrong and I need some fresh ideas or working solution. Can anyone help with this?

Here is some code that shows minimal 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;
}

How can I improve this or I should find another ideas?

4
  • 5
    Show some code...
    – acraig5075
    Feb 20, 2020 at 12:45
  • 1
    asking for ideas is too vague and open-ended, better provide a minimal reproducible example of your idea that didnt work Feb 20, 2020 at 13:05
  • Start with looking at the Hamming Distance. It's not quite the same, as there is no sequence of steps that gets you from "aa" to "ab"
    – Caleth
    Feb 20, 2020 at 13:13
  • At least: if A contains a letter l at position i and j, it is impossible if word B contains two different letters at i and j. Feb 20, 2020 at 13:26

1 Answer 1

0

First of all, don't worry about string operations. Your problem is algorithmic, not textual. You should somehow analyze your data, and only afterwards print your solution.

Start with building a data structure which tells, for each letter, which letter it should be replaced with. Use an array (or std::map<char, char> — it should conceptually be similar, but have different syntax).

If you discover that you should convert a letter to two different letters — error, conversion impossible. Otherwise, count the number of non-trivial cycles in the conversion graph.

The length of your solution will be the number of letters which shouldn't be replaced by themselves plus the number of cycles.

I think the code to implement this would be too long to be helpful.

2
  • Thank you for answer, so it doesn't matter in what order the letters are, I just need to build simple comparation matrix using map<char, char>?
    – Vakhit
    Feb 20, 2020 at 15:32
  • I guess it is important in what order the letters are. But yes, you should first build a conversion table using map<char, char> (but you can also use an array char[26]), and when you have it, you can forget about the initial string.
    – anatolyg
    Feb 20, 2020 at 17:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.