Inverse of StringReplace

rules = {"a" -> "0", "OverBar[a]" -> "1", "b" -> "1", 
   "OverBar[b]" -> "0", "c" -> "0", "OverBar[c]" -> "1", "d" -> "0", 
   "OverBar[d]" -> "1", "e" -> "0", "OverBar[e]" -> "1"};
str = "10000";

StringReplaceList[#, Reverse /@ rules] & /@ StringPartition[str, 1];
Outer[StringJoin, Sequence@@%] // Flatten;

MemberQ[%, #] & /@ {"bcccc", "bcccd", "bccde"}

{True, True, True}

The number of solutions

Length[%%]

3125

With a large number of replacement rules it would be slow to find all of them, but you could find a sample of them like this:

inverses = Reap[Do[
      Sow[StringReplace["10000", RandomSample[Reverse /@ rules]]]
      , 100]][[-1, 1]] // DeleteDuplicates;

Results:

OverBar[d]dddd
OverBar[c]OverBar[b]OverBar[b]OverBar[b]OverBar[b]
OverBar[c]eeee
OverBar[a]dddd
OverBar[d]eeee
OverBar[a]cccc
OverBar[d]OverBar[b]OverBar[b]OverBar[b]OverBar[b]
OverBar[e]eeee
OverBar[a]OverBar[b]OverBar[b]OverBar[b]OverBar[b]
OverBar[c]dddd
OverBar[a]eeee
OverBar[e]cccc
bdddd
OverBar[d]cccc
OverBar[d]aaaa
OverBar[e]OverBar[b]OverBar[b]OverBar[b]OverBar[b]
OverBar[a]aaaa
OverBar[c]aaaa
OverBar[e]aaaa
bcccc
beeee
baaaa
OverBar[e]dddd

Confirm that they work:

StringReplace[inverses, rules]

(* result: {"10000", "10000", "10000", "10000", "10000", "10000", "10000", 
"10000", "10000", "10000", "10000", "10000", "10000", "10000", 
"10000", "10000", "10000", "10000", "10000", "10000", "10000", 
"10000", "10000", "10000", "10000"} *)