0

I have two words nice and niece. How do i figure out e is missing to make both words the same.

Also say i have from and form. How do i return/figure out the letter r o has to be swap to make the words the same.

What i really want is a php that does whats in the image below.

I tried using built-in PHP functions for string manipulation, but none seem to be able to accomplish what i want.

Any help will be greatly appreciated.

W3Guy
  • 657
  • 1
  • 7
  • 16
  • 1
    Numerically, this is known as the [Levenshtein distance](https://en.wikipedia.org/wiki/Levenshtein_distance). You may be able to modify the algorithm which computes the distance to instead yield the actual differences. – Mr. DOS Jul 09 '15 at 15:26
  • Still in my first year in Comp. Sci. Mind helping me modifying it? FYI i couldnt make sense of the principle. – W3Guy Jul 09 '15 at 15:34
  • Not really my strong point, sadly. Try asking in the [algorithm](http://stackoverflow.com/questions/tagged/algorithm) tag; they may be able to point you in the right direction. The question you're asking isn't really PHP-specific: you're not running into a problem implementing some method. The problem is that you don't know (and for that matter, I don't know) the method to use in the first place. – Mr. DOS Jul 09 '15 at 15:45
  • Here http://stackoverflow.com/questions/321294/highlight-the-difference-between-two-strings-in-php you can find many libraries and examples about how to start – Filo Jul 09 '15 at 15:50
  • Thanks Filo. i will check and hope they come in handy. – W3Guy Jul 09 '15 at 16:01
  • Given the usage of php (?!?!), I have to ask - 1st year comp sci of what kind of program ? – gen-y-s Jul 09 '15 at 16:56
  • Why is the function returning impossible in the last case? Can't it say `INSERT dd`? You gave 3 different cases, and I can't wrap my mind to come up with a single problem statement that will include all 3 cases... So, you can `swap` and `insert`, shoud it be only a `swap` or an `insert` or you can combine, can you have multiple `swaps`, can you have multiple `inserts`, should the `swap`be only from consecutive letters.? – Alexandru Barbarosie Jul 09 '15 at 22:18

1 Answers1

0

what you're looking for is optimal alignment. simplest way to compute it is Needleman–Wunsch algorithm. for bigger inputs you will need something better but more complicated: Hirschberg's algorithm (which has better memory complexity). or simply get some diff library written in your language

however you won't get 'impossible' result as each word can be changed to other word using deletions, insertions and changes. if you need different constraints you would have to modify above algorithms and use your own metrics and/or operations

piotrek
  • 13,982
  • 13
  • 79
  • 165