Hi,

die möglichen Reihenfolgen könntest Du im Regex berücksichtigen; also nach diesem Schema: m/foo.*bar|bar.*foo/

Was die Erkennung der Rechtschreibfehler angeht, sehe ich das nicht so einfach zu lösen.
Wenn die möglichen Fehler bekannt sind, könntest Du sie als Varianten auch im Regex berücksichtigen.

Wenn es unbekannte Fehler sind, dann wird es schwieriger.
Vielleicht vor der Analyse eine Rechtschreibprüfung durchführen lassen und die Texte korrigieren.
Danach die Regex-Suche auf die korrigierten Texte anwenden?