Check if a string substitution rule will ever generate another string.

Question

Not homework.

Given two strings S and T of same length. Given a set of replacement rules, that find substring A in S and replace it with string B. A and B have the same length.

Is there a sequence of rule application, such that it make string S into string T?

Example: We have replacement rules

cat->dog
dog->cut

we have string S1:awesomecat and S2:awesomecut

A sequence of replacement can be

awesomecat 
awesomedog cat->dog
awesomecut dog->cut

That's a easy example, it's possible there are rules like this.

cat->dog
ate->dog
dog->cat

I believe there is no better way to answer this than try every single rule in every single state. Which would be exponential time. But I don't know if there are better solutions to it.

Answer 1

You can easily map this problem to a directed graph in which all rules are directed paths from one node to another.

Upon receiving inputs A and B, check the diff between them, and see if you have a path along the graph that yields expected result.