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?