Logic - Given 2 strings, how to know how many moves I make when turning the first string into the second

Asked

Viewed 53 times

1

Hi, are you okay? I have 2 strings , and I need you to calculate the total of moves to become the first string in the second string

string palavra1 = "gato"
string palavra2 = "pato"

replacing the "G" of the "P" cat, I turn "cat" into "duck".

but it could also be strings

string palavra1 = "cavalo";
string palavra2 = "pato";

In that case the total of movements would be 4. because it would remove C(1) and A(2) and exchange V for P(3) and L for T(4)

Can someone help me? Abs,

  • Hi, I’m not familiar with C# (I only work with Javascript), but try looking for some kind of function/library that does something like the site Diff Checker. In this webapp you put two data: one original text and the other changed. After checking, the number of letters removed would be like the number of drives you mentioned. Obs.: For test purposes, put one letter per line. Surely there must be an implementation in your language.

1 answer

0

An algorithm that does this is Greater Common Subsequence or in English Longest Common Subsequence.

The first link, I had to point to a Google search, because I could not find a more immutable reference. In the second, goes to the Wikipedia page in English... but there are some examples of implementation there.

This algorithm can be used to compare any type of sequence, such as two strings, two lists of strings representing the lines of two texts, etc.

  • Thanks for the answer Miguel, reading here is the logic I need to do...but the problem is to fit this logic in my code c#.

  • After Miguel’s reply, I went to research on Longest Common Subsequence and found this article that helped me a lot. https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Longest_common_subsequence Valeu...

  • Cool this site! ... Reviewing your question, if you are only interested in the amount of changes, you can also search about Levenshtein Distance (Distance Levenshtein)

  • Someone comes negative and doesn’t say anything... it’s boring to answer at SOPT lately!

Browser other questions tagged

You are not signed in. Login or sign up in order to post.