Using re doesn't harm in any way, but just for scientific curiosity, another approach that doesn't require you to pass through re is using sets:
>>> valid = set('ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_ ')
>>> def test(s):
... return set(s).issubset(valid)
...
>>> test('ThiS iS 4n example_sentence that should-pass')
True
>>> test('ThiS iS 4n example_sentence that should fail!!')
False
For conciseness, the testing function could also be written:
>>> def test(s):
... return set(s) <= valid
EDIT: A bit of timing for the sake of curiosity (times are in seconds, for each test implementation it runs three sets of iterations):
>>> T(lambda : re.match(r'^[a-zA-Z0-9-_]*$', s)).repeat()
[1.8856699466705322, 1.8666279315948486, 1.8670001029968262]
>>> T(lambda : set(y) <= valid).repeat()
[3.595816135406494, 3.568570852279663, 3.564558982849121]
>>> T(lambda : all([c in valid for c in y])).repeat()
[6.224508047103882, 6.2116711139678955, 6.209425926208496]