[Beldin]

If you have the regex, you'd use it to generate candidate strings. Then, of course you don't have to check any more.

For a more complex regex, you could resort to a simplified version (eg, with larger search space). But the space of all random strings is way too huge to just generate random bitstrings and hope they match the regex.