e.g distance between *cd* and abcdef should be 0.

I hope you're aware that *cd* isn't a valid regex? * is a quantifier, and can't stand at the start of a regex. Maybe you mean globs instead? (The wildcards that you use on the command line).

Update: More importantly, do you want your problem to be solved for regex, or for globs?

Another update: Do you want the edit distance between two globs/regex, or between one and a target string?