  # convert one string to another such that one char is changed at a time?

161 views

How to convert one string to another such that only one character is changed at a time and after each change the transformed string is in the dictionary. You need to do this in the minimum number of transformations. For example the transformation from rat-->boy can be done as follows:

`````` rat-->bat-->bot-->boy (if dictionary has bat and bot)
``````

Any suggestion on how to achieve this? posted Nov 26, 2013

After each change (one character at a time)there may be a string which is not in dictionary at all. In programming concern we would require to check whether the new string is in the dictionary or not? to check the string we need to have a array of strings,containing all the dictionary words,in practical it is not possible to create such string in programming languages like C, although it can be achieved if the user defined dictionary, of some limited words is used. answer Mar 16, 2016
Similar Questions

Convert the given string into palindrome with minimum number of appends(at end of the given string). O(n) algorithm will be appreciated ??

Input :=> Malayal
Output :=> Malayalam

Given 2 strings s1, s2 and s1 is equal to s2 if they are lexicographically sorted, Find minimum number of swaps required to transform s1 to s2?

Swap Definition:
Problem 1 : we can transform index i with i+1 where 0<=i< s1.length()-1
Problem 2 : we can transform index i with i+1 where 0<=i< s1.length()-1 and other operation we can swap first character of string with last

example: s1="abc", s2="cba"
In problem1 3 swaps required abc ---> bac ---> bca ---> cba
In problem2 1 swaps required abc ---> cba [swap first and last element]

Given a dictionary of strings and another string find out if the string is an exact match to some words in the dictionary or varies at most in only one place of some word of the dictionary?