Datentypen Verdrehte Wörter wieder herstellen

CptK

Bekanntes Mitglied
Servus, ich habe einen Text bestehen aus verdrehten Wörtern z.B.: "Blad feil ihr Auge auf eine klenie Gaslbüchse, die unter dem Tcsihe lag". Der erste und der letzte Buchstabe sind im Wort jeweils richtig, was heißt mich interessieren nur die Wörter mit mehr als 3 Zeichen. Zudem habe ich eine Wörterliste (pro Zeile ein Wort). Jetzt möchte ich ein Programm haben, dass mit Hilfe der Liste die verdrehten Wörter erschließt.
Ich weiß leider nicht genau wie ich da rangehen soll, bin also für jede Hilfe dankbar.

Ich habe das jetzt folgendermaßen versucht:
Java:
private ArrayList<String> words = new ArrayList<String>();
    private ArrayList<String> untwistedWords = new ArrayList<String>();
    private ArrayList<String> wörterbuch = new ArrayList<String>();

Java:
private void untwist(int wordNr) {
        char n[] = words.get(wordNr).toCharArray();
        if(n.length > 3) {
        
            for(int i = 0; i < wörterbuch.size(); i++) {
                char w[] = wörterbuch.get(i).toCharArray();
                if(n.length == w.length) {
                    if(n[0] == w[0]) {
                        if(n[n.length-1] == w[w.length-1]) {
                        
                        }
                    }
                }
            }
        
        } else {
            untwistedWords.add(words.get(wordNr));
        }
    }

Ich wandel mir die Wörter in Chararrays um und gehe dann die Wörterliste durch, ob die Wörter dort gleich lang sind und der erste und der letzte Buchstabe gleich sind. Das grenzt das Ganze zwar schon etwas ein, ist aber nicht genau genug. Jetzt würde ich einfach hingehen und überprüfen, ob alle Buchstaben von n[] enthalten sind.
Ich weiß jetzt aber leider nicht, wie ich das ganze am besten umsetzen soll.
 
Zuletzt bearbeitet:

max40

Bekanntes Mitglied
eine Möglichkeit die aber optimiert werden sollte, damit das sortieren nicht so oft gemacht werden muss:
Java:
 ...
if(n[n.length-1] == w[w.length-1]) {

    Arrays.sort(w, 1, w.length-1);
    Arrays.sort(n, 1, n.length-1);
    if (Arrays.equals(w,  n)){
        untwistedWords.add(wörterbuch.get(i));
        return;
    }
  
}
...
 

Robat

Top Contributor
Wie schon in deinem anderen Thread geschrieben, kannst du hierzu die Levenshtein-Distanz benutzen.
Java:
public class Untangler {
    private List<String> dictionary;

    public Untangler(List<String> dictionary) {
        this.dictionary = dictionary;
    }

    public String untangleAndGet(String twistedSentence) {
        StringBuilder builder = new StringBuilder(twistedSentence.length());

        for (String word : twistedSentence.split(" ")) {
            if (word.length() > 3) {
                Optional<String> actualWord = dictionary.stream().min(Comparator.comparingInt(o -> computeLevenshteinDistance(word, o)));
                actualWord.ifPresent(builder::append);
            } else {
                builder.append(word);
            }
            builder.append(" ");
        }
        return builder.toString();
    }

    private int minimum(int a, int b, int c) {
        return Math.min(Math.min(a, b), c);
    }

    private int computeLevenshteinDistance(String first, String second) {
        int[][] distance = new int[first.length() + 1][second.length() + 1];

        for (int i = 0; i <= first.length(); i++) {
            distance[i][0] = i;
        }

        for (int j = 1; j <= second.length(); j++) {
            distance[0][j] = j;
        }

        for (int i = 1; i <= first.length(); i++) {
            for (int j = 1; j <= second.length(); j++) {
                int match = (first.charAt(i - 1) == second.charAt(j - 1)) ? 0 : 1;
                distance[i][j] = minimum(
                        distance[i - 1][j] + 1,
                        distance[i][j - 1] + 1,
                        distance[i - 1][j - 1] + match);
            }
        }

        return distance[first.length()][second.length()];
    }
}
An einem einfachen Beispiel getestet:
Java:
String sentence = "Java ist eine komplexe Programmiersprache die zur Entwicklung von Anwendungen geeignet ist.";
List<String> dictionary = Arrays.asList(sentence.split(" "));

Untangler entwister = new Untangler(dictionary);
String twistedSentence = "Jvaa ist eine kpomlxee Prorgmmaeirpsarhce die zur Enwtikclnug von Anwendungen geeignet ist.";

System.out.println("Original : " + sentence);
System.out.println("Twisted  : " + twistedSentence);
System.out.println("Entwisted: " + entwister.untangleAndGet(twistedSentence));
liefert folgende Ausgabe:
Code:
Original : Java ist eine komplexe Programmiersprache die zur Entwicklung von Anwendungen geeignet ist.
Twisted  : Jvaa ist eine kpomlxee Prorgmmaeirpsarhce die zur Enwtikclnug von Anwendungen geeignet ist.
Entwisted: Java ist eine komplexe Programmiersprache die zur Entwicklung von Anwendungen geeignet ist.
 
X

Xyz1

Gast
Sind die Buchstaben der Wörter eigentlich vermischt oder gedreht? Weil ich bin von gemischt ausgegangen....
Das ändert natürlich alles!
 

Meniskusschaden

Top Contributor
Wie schon in deinem anderen Thread geschrieben, kannst du hierzu die Levenshtein-Distanz benutzen.
Das funktioniert noch nicht ganz richtig. Beispiel:
Java:
public static void main(String[] args) {
    String sentence = "Haftung Haltung Sichtung Dichtung";
    List<String> dictionary = Arrays.asList(sentence.split(" "));

    Untangler entwister = new Untangler(dictionary);
    String twistedSentence = "Hatlung Sxchtung Dichtugn";

    System.out.println("Original : " + sentence);
    System.out.println("Twisted  : " + twistedSentence);
    System.out.println("Entwisted: " + entwister.untangleAndGet(twistedSentence));
}
Ausgabe:
Code:
Original : Haftung Haltung Sichtung Dichtung
Twisted  : Hatlung Sxchtung Dichtugn
Entwisted: Haftung Sichtung Dichtung

Aus "Hatlung" hätte "Haltung" und nicht "Haftung" werden müssen, "Sxchtung" (x ist falsch) und "Dichtugn" (Endbuchtstabe nicht gleich) hätten gar nicht übersetzt werden dürfen.

Sind die Buchstaben der Wörter eigentlich vermischt oder gedreht? Weil ich bin von gemischt ausgegangen....
Ich bin von (auch mehrfachen) Verdrehungen ausgegangen, so dass die inneren Buchstaben letztendlich beliebig vertauscht sein können, aber in der jeweils korrekten Anzahl vorhanden sein müssen.
 

CptK

Bekanntes Mitglied
Also es soll so sein, dass die Wörter so geändert werden, dass der erste und der letzte Buchstabe gleich bleiben und die Wörter in der Mitte werden untereinander getauscht, jedoch nicht mit anderen Wörtern.
Das Wort "Hallo" zum Beispiel ist getwistet also "Hlalo" oder "Hllao".
 

Robat

Top Contributor
Das mit den Endbuchstaben hab ich ganz überlesen. Jetzt sollten eigentlich alle Fälle abgedeckt sein, oder?
Java:
public class Untangler {

    private List<String> dictionary;

    public Untangler(List<String> dictionary) {
        this.dictionary = dictionary;
    }

    public String untangleAndGet(String twistedSentence) {
        StringBuilder builder = new StringBuilder(twistedSentence.length());

        for (String word : twistedSentence.split(" ")) {
            Optional<String> actualWord = dictionary.stream()
                    .filter(otherWord -> hasMinimumLength(otherWord) &&
                            haveSameLetters(word, otherWord) &&
                            areSurroundedWithSameLetters(word, otherWord))
                    .min(Comparator.comparingInt(o -> computeLevenshteinDistance(word, o)));
            actualWord.ifPresentOrElse(builder::append, () -> builder.append(word));
            builder.append(" ");
        }
        return builder.toString();
    }

    private boolean hasMinimumLength(String word) {
        return word.length() > 3;
    }

    private boolean areSurroundedWithSameLetters(String firstWord, String secondWord) {
        return firstWord.charAt(0) == secondWord.charAt(0) &&
                firstWord.charAt(firstWord.length() - 1) == secondWord.charAt(secondWord.length() - 1);
    }

    private boolean haveSameLetters(String firstWord, String secondWord) {
        char[] lettersFirstWord = firstWord.toCharArray();
        char[] lettersSecondWord = secondWord.toCharArray();
        Arrays.sort(lettersFirstWord);
        Arrays.sort(lettersSecondWord);

        return Arrays.equals(lettersFirstWord, lettersSecondWord);
    }

    private int min(int a, int b, int c) {
        return Math.min(Math.min(a, b), c);
    }

    private int computeLevenshteinDistance(String first, String second) {
        int[][] distance = new int[first.length() + 1][second.length() + 1];

        for (int i = 0; i <= first.length(); i++) {
            distance[i][0] = i;
        }

        for (int j = 1; j <= second.length(); j++) {
            distance[0][j] = j;
        }

        for (int i = 1; i <= first.length(); i++) {
            for (int j = 1; j <= second.length(); j++) {
                int match = (first.charAt(i - 1) == second.charAt(j - 1)) ? 0 : 1;
                distance[i][j] = min(
                        distance[i - 1][j] + 1,
                        distance[i][j - 1] + 1,
                        distance[i - 1][j - 1] + match);
            }
        }

        return distance[first.length()][second.length()];
    }
}
 

Robat

Top Contributor
Das einzige wo es sehr wahrscheinlich nicht klappen würde, wäre bei Anagrammen die mit dem gleichen Buchstaben anfangen / aufhören. Zum Beispiel bei ["Asche", "Achse"] .. nur fällt mir da auch spontan nichts ein um das zu prüfen.
Code:
Original : Asche Achse
Twisted  : Acshe Ahcse
Entwisted: Asche Asche
 

mihe7

Top Contributor
@Robat @Meniskusschaden was mir gerade nicht ganz klar ist: wenn ich davon ausgehe, dass die inneren Buchstaben zufällig vertauscht sind, was bringt dann die an
Java:
Optional<String> actualWord = dictionary.stream()
                    .filter(otherWord -> hasMinimumLength(otherWord) &&
                            haveSameLetters(word, otherWord) &&
                            areSurroundedWithSameLetters(word, otherWord))
anschließende Ähnlichkeitssuche?
 

Meniskusschaden

Top Contributor
@Robat @Meniskusschaden was mir gerade nicht ganz klar ist: wenn ich davon ausgehe, dass die inneren Buchstaben zufällig vertauscht sind, was bringt dann die an
...
anschließende Ähnlichkeitssuche?
Ich weiß nicht, ob es hier wirklich etwas bringt. Kommt eben darauf an, ob in dem Anwendungsfall die Intensität der Unordnung umgekehrt proportional zur Treffer-Wahrscheinlichkeit ist. Als Anwender würde ich bei Mehrdeutigkeiten wahrscheinlich lieber die Alternativen sehen und selbst entscheiden.
 

mihe7

Top Contributor
Ich seh das so: ich habe ein verdrehtes Wort, dann gibt es im Wörterbuch entweder
  1. nur eine Permutation des Worts, dann ist die Sache eindeutig und ich kann mir die Ähnlichkeitssuche sparen,
  2. oder mehrere Permutationen des verdrehten Wortes. Da aber alle Permutationen gleich wahrscheinlich sind, kann ich eine beliebige wählen und mir die Ähnlichkeitssuche sparen.
 

Robat

Top Contributor
Jetzt merk ich erst worauf du (und wahrscheinlich auch der TE) hinaus willst.
Bin irgendwie davon ausgegangen, dass neben verdrehten Buchstaben auch falsche Buchstaben vorkommen können.. dem ist ja aber nicht so.

Indem Fall würde die Ähnlichkeitssuche tatsächlich überflüssig sein.

Bleibt die Frage wie man mit Anagrammen umzugehen hat. (Asche, Achse)
 

max40

Bekanntes Mitglied
Warum machst du erst ein Substring um dann das array zu sortieren?
Hast du dir überhaupt mein Lösungsvorschlag von gestern angeschaut?
Beim sort kannst du den Bereich mitgeben, welchen er sortieren soll.
 
X

Xyz1

Gast
Etwas eher :)
Beim sort kannst du den Bereich mitgeben, welchen er sortieren soll.

Ja ist besser....
Java:
    String sortB(String s) {
        char[] a = s.toCharArray();
        Arrays.sort(a, 1, a.length-1);
        return String.valueOf(a);
    }

Habe eine Benchmark hier erstellt.
Code:
Benchmark                 Mode  Cnt     Score   Error   Units
MyBenchmark.testMethodA  thrpt       1460.738          ops/ms
MyBenchmark.testMethodB  thrpt       1784.005          ops/ms

1/6 ungefähr....
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
julian0507 Wörter einlesen lassen und rückwärts ausgeben Java Basics - Anfänger-Themen 7
B String - Wörter finden, welches Punkt und entsprechender Pre / Suffix hat? Java Basics - Anfänger-Themen 30
Z Satz aufteilen und die Wörter zählen (HashMap) Java Basics - Anfänger-Themen 15
M Regex für bestimmte Wörter bzw. bestimmte Zeichen erstellen Java Basics - Anfänger-Themen 5
N Wörter und Zahlen nach speziellen Wörtern ausgeben Java Basics - Anfänger-Themen 11
S spezielle Wörter aus Liste entfernen Java Basics - Anfänger-Themen 2
J Wörter aus Textdatei suchen Java Basics - Anfänger-Themen 2
CptK Variablen Wörter erschließen Java Basics - Anfänger-Themen 7
B String: suche nach Wörter und in List<String> speichern Java Basics - Anfänger-Themen 3
Orkanson Methoden String in Wörter zerlegen und Endungen der Wörter überprüfen. Java Basics - Anfänger-Themen 4
JavaNewbie2.0 Tausende Wörter in Arrays automatisch einfügen Java Basics - Anfänger-Themen 10
B Collections Java Wörter in String zählen und geordnet ausgeben Java Basics - Anfänger-Themen 10
E Datei einlesen und bestimmte Wörter ausgeben Java Basics - Anfänger-Themen 2
DestinatioN Problem beim splitten eines Satzes in Wörter und die Wörter in Buchstaben Java Basics - Anfänger-Themen 2
A Wie am effizientesten bzw. schnellsten Namen/Wörter sortieren? Java Basics - Anfänger-Themen 1
I String teilen und zwei Wörter generieren Java Basics - Anfänger-Themen 1
A Text teilen und Wörter zählen Java Basics - Anfänger-Themen 7
I String trennen und verschiedene Wörter holen Java Basics - Anfänger-Themen 6
T Eingegebene Wörter ausgeben? Java Basics - Anfänger-Themen 3
T Wörter mit @ als Zeichen finden Java Basics - Anfänger-Themen 13
J Alle Wörter der Länge n mit 0 und 1 Java Basics - Anfänger-Themen 17
G wörter speichern Java Basics - Anfänger-Themen 12
T Erste Schritte einzelne Wörter aus textdatei lesen... Java Basics - Anfänger-Themen 4
C Wörter aus einer txt datei lesen Java Basics - Anfänger-Themen 19
C String Arrays - häufigste Wörter Java Basics - Anfänger-Themen 10
T Erste Schritte Eingelesenen Satz - Wörter und Leerzeichen getrennt in 2x Array's Java Basics - Anfänger-Themen 7
B Input/Output Wörter zählen & sortieren Java Basics - Anfänger-Themen 9
S Buchstaben/Wörter im String zählen Java Basics - Anfänger-Themen 6
K Anzahl Wörter in Zeile Java Basics - Anfänger-Themen 24
F wörter trennen und in txt-file schreiben Java Basics - Anfänger-Themen 5
J Von einem String einzelne Wörter speichern Java Basics - Anfänger-Themen 6
R Wörter-KarteiSystem/Vokabel Trainer Source Fragen Java Basics - Anfänger-Themen 9
A Wörter umgekehrten Reihenfolge ausgeben Java Basics - Anfänger-Themen 3
J Wörter in einem string zählen und die anzahl zurückgeben Java Basics - Anfänger-Themen 4
P Zwei Wörter vergleichen Java Basics - Anfänger-Themen 11
S Wörter zählen Java Basics - Anfänger-Themen 19
N Wörter zählen im String Java Basics - Anfänger-Themen 3
Screen Wie lese ich Wörter ein? Java Basics - Anfänger-Themen 6
G Wörter Zählen Java Basics - Anfänger-Themen 11
J Wörter im String zählen Java Basics - Anfänger-Themen 4
P wörter im string zählen Java Basics - Anfänger-Themen 9
G Häufigkeit der Wörter einer Webseite zählen Java Basics - Anfänger-Themen 7
C Wörter suchen Java Basics - Anfänger-Themen 4
M Anzahl von Wörter in einer eingelesenen Datei Java Basics - Anfänger-Themen 10
S Regex, Wörter ersetzen Java Basics - Anfänger-Themen 2
S Welche Bedeutung haben diese Wörter? Java Basics - Anfänger-Themen 2
S Zeilen, Zeichen, Wörter Java Basics - Anfänger-Themen 3
K Wörter zählen auf Internetseiten... die zweite Java Basics - Anfänger-Themen 4
DrahtEck Schleife soll wieder da anfangen wo ich es möchte ! Java Basics - Anfänger-Themen 17
G JTree speichern und wieder einlesen Java Basics - Anfänger-Themen 5
W In alten Code zurück- und dort wieder zurechtfinden? Java Basics - Anfänger-Themen 17
I Passwort in Datenbank speichern um später wieder auszulesen Java Basics - Anfänger-Themen 5
Temsky34 Wie bekomme ich dieses Java-Warning wieder weg? Java Basics - Anfänger-Themen 2
T j.u.Scanner(Sys.in).nextLine() wieder schließen? Java Basics - Anfänger-Themen 5
f3mys Objektwerte in Liste speichern und wieder abrufen Java Basics - Anfänger-Themen 23
O Text mit Regex trennen und wieder zusammenbauen Java Basics - Anfänger-Themen 5
Naxon89 Input/Output Ein PDF in einem BLOB umwandeln um ihn dann als PDF wieder anzuzeigen Java Basics - Anfänger-Themen 3
H JavaFX Hintergrundfarbe ändern, warten, Hintergrundfarbe wieder ändern Java Basics - Anfänger-Themen 34
MichelNeedhelp Brauche zu diesem Labyrinth ein Skript? Der Hamster soll im Urzeigersinn das ganze Labyrinth abgehen und wieder an seinem Ursprungsplatz sein. Java Basics - Anfänger-Themen 40
D Codeblöcke, die immer wieder im Programmverlauf benötigt werden Java Basics - Anfänger-Themen 5
TimoN11 Array -> Schleife wieder von vorne durchlaufen lassen Java Basics - Anfänger-Themen 1
JD_1998 Arrays einlesen, zwischenspeichern und wieder ausgeben Java Basics - Anfänger-Themen 8
M Regex Probleme (mal wieder) Java Basics - Anfänger-Themen 3
J Selektiertes Element von jComboBox zwischenspeichern und wieder einsetzen Java Basics - Anfänger-Themen 0
S Nutzereingabe splitten und in string array wieder ausgeben. Java Basics - Anfänger-Themen 1
I wieder mit einer Umwandelung habe ich Problem (diesmal von char Array zu char) Java Basics - Anfänger-Themen 1
N Wie kann ich einen String wieder zusammensetzen und ausgeben lassen? Java Basics - Anfänger-Themen 9
C Array-Eintrag wieder auf Null setzen Java Basics - Anfänger-Themen 3
W Verschachtelte Objekte wieder auspacken Java Basics - Anfänger-Themen 3
M Array immer wieder um ein Element erweitern Java Basics - Anfänger-Themen 6
CptK Methoden Event bei gedrückter Maustaste immer wieder ausführen Java Basics - Anfänger-Themen 1
CptK Klassen Event bei gedrückter Maus immer wieder mit Pause ausführen Java Basics - Anfänger-Themen 2
J Geld speichern und wieder auslesen Java Basics - Anfänger-Themen 10
M JTextField blitzt immer wieder nur auf Java Basics - Anfänger-Themen 12
J Timer bauen, Main Methode immer wieder neu starten Java Basics - Anfänger-Themen 13
I Methoden Schleife immer wieder durchlaufen lassen Java Basics - Anfänger-Themen 15
F Immer wieder gleiche Zufallszahl? Java Basics - Anfänger-Themen 4
M Schleifenergebnis in selbiger wieder verwenden Java Basics - Anfänger-Themen 7
L Methoden Rekursion gibt alten Wert wieder Java Basics - Anfänger-Themen 37
L jar, class, java und wieder zurück Java Basics - Anfänger-Themen 8
M aus Fenster anderes Fenster öffnen und wieder umgekehrt Java Basics - Anfänger-Themen 5
J Fenster wieder unsichtbar machen Java Basics - Anfänger-Themen 2
J Auslesen/speichern und wieder einlesen Java Basics - Anfänger-Themen 7
S Sound stoppen und nach Pause wieder abspielen Java Basics - Anfänger-Themen 6
T while schleife starten , beeneden und wieder Starten Java Basics - Anfänger-Themen 8
I Zähler, der erst wieder zählt nachdem Pixel wieder andere Farbe hat Java Basics - Anfänger-Themen 2
B javax.ejb.Timer wieder starten? Java Basics - Anfänger-Themen 0
N Methode auslagern mal wieder Java Basics - Anfänger-Themen 8
F Inhalt einer Variable auswerten, die sich immer wieder ändert Java Basics - Anfänger-Themen 1
B ja ja schon wieder einer mit einer public static void main(string[] args) Frage... Java Basics - Anfänger-Themen 8
Bluedaishi for schleife um Dateien wieder zusammen zu fügen Java Basics - Anfänger-Themen 11
I SHA512 verschlüsseln und dann wieder auslesen? Java Basics - Anfänger-Themen 35
F Timer abbrechen und wieder starten Java Basics - Anfänger-Themen 5
J KeyListener - mal wieder... Java Basics - Anfänger-Themen 2
B Listener beim Laden (deserialize) wieder hinzufügen bzw. mitspeichern? Java Basics - Anfänger-Themen 3
GadgetSofa .txt Datei erstellen und gleich wieder Löschen? Java Basics - Anfänger-Themen 12
D Bild für ein paar Sekunden einblenden und wieder ausblenden Java Basics - Anfänger-Themen 1
M Tabelle aktualisieren (mal wieder) Java Basics - Anfänger-Themen 10
M Erste Schritte Tabelle aktualisieren (mal wieder) Java Basics - Anfänger-Themen 7
M Zahlen als Bytes in eine Datei speichern, daraus wieder auslesen Java Basics - Anfänger-Themen 2

Ähnliche Java Themen

Neue Themen


Oben