Another interesting puzzle :-

Transform One String to Another

Let S and T be strings and D a set of strings. You can say that S produces T if there exists a sequence of strings, SEQ=[s1, s2, …, sn-1] which meets these criteria:

  • s0 = S

  • sn-1 = T

  • All members of SEQ belong to set D

  • Adjacent strings have the same length and differ in exactly one character.

For example, given the set {“cat”, “bar”, “bat”}, you can say that “cat” produces “bar” by

[“cat”, “bat”, “bar”]

Or, given the set {“cat”, “red”, “bat”}, you can say that “cat” does not produce “red”.

Given a set D and two strings S and T, write a function to determine if S produces T. Assume that all > characters are lowercase letters. If S does produce T, output the length of a shortest production sequence; otherwise, output -1.

Click to view my solution

blog comments powered by Disqus