Wenn ich zwei Strings gleicher Länge wie folgt habe:
%Vor%Gibt es eine effiziente Möglichkeit, die beiden so auszurichten, dass möglichst viele Buchstaben wie unten gezeigt ausgerichtet sind?
%Vor%Der einzige Weg, wie ich mir das vorstellen kann, ist Brute-Force, indem ich die Strings editiere und dann wiederhole und vergleiche.
Geben Sie den Index zurück, der die maximale Punktzahl angibt, wobei die maximale Punktzahl die Zeichenfolgen mit den meisten übereinstimmenden Zeichen ist.
%Vor%Oder äquivalent:
%Vor%Es gibt Raum für Optimierungen wie:
Früher Ausgang für keine übereinstimmenden Zeichen
Früherer Ausgang, wenn die maximal mögliche Übereinstimmung gefunden wurde
Ich bin nicht sicher, was Sie mit effizient meinen, aber Sie können die Methode find für str:
Ich kann keinen anderen Weg sehen, als brutales Zwingen es. Die Komplexität wird in der String-Länge quadratisch sein, was akzeptabel sein kann, abhängig davon, mit welchen String-Längen Sie arbeiten.
Etwas wie das vielleicht:
%Vor% Ich würde so etwas wie die binäre Funktion & für jeden Ihrer Strings tun. Vergleicht jeden der Strings, wenn sie aufgereiht sind, und zählt die Anzahl der Übereinstimmungen von Buchstaben hoch. Dann schalte um eins und mache dasselbe, und fahre fort mit dem Verschieben, bis sie nicht mehr aufgereiht sind. Die Verschiebung mit den passendsten Buchstaben auf diese Art und Weise ist die korrekte Ausgabeverschiebung, und Sie können die Striche hinzufügen, wenn Sie sie ausdrucken. Sie müssen die Zeichenfolgen nicht wirklich ändern, sondern nur die Anzahl der Verschiebungen zählen und den Vergleich der Zeichen um den Verschiebungsbetrag korrigieren. Das ist nicht besonders effizient (O (n ^ 2) = n + (n-2) + (n-4) ...), aber es ist das Beste, was ich mir vorstellen kann.
Tags und Links python string-comparison