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

Posted by Mgccl on Stack Overflow See other posts from Stack Overflow or by Mgccl
Published on 2010-06-17T22:18:43Z Indexed on 2010/06/17 22:23 UTC
Read the original article Hit count: 233

Filed under:

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?

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.

© Stack Overflow or respective owner

Related posts about algorithm