suchen

Wortsuche II

Sep 25, 2024 am 06:15 AM

Word Search II

Problem

Intuition: Da wir Wörter (auf dem Raster/der Tafel) finden müssen, die im Wortarray vorhanden sind, indem wir nach oben/unten/links/rechts blättern.
Die Durchquerung kann mittels Backtracking
erfolgen Für die Suche nach dem Wort können wir trie verwenden, da uns dies auch bei der Früherkennung hilft, indem wir prüfen, ob ein Präfix im Baum vorhanden ist oder nicht. Dadurch wird ein unnötiges Durchqueren der Tafel vermieden (d. h. es hat keinen Sinn, die Tafel zu durchqueren, denn wenn das Präfix nicht im Trie vorhanden ist, ist die Zeichenfolge oder Wortform, die das Präfix verwendet, auch nicht im Trie vorhanden)

Ansatz: Wir werden alle Wörter[] in den Trie einfügen, dann werden wir das Brett für jede Zelle (i,j) durchqueren und in alle 4 Richtungen gehen, um verschiedene Zeichenfolgen zu bilden, und wir werden alle einfügen Zeichenfolgen, die im Versuch vorhanden sind, in einer Liste.

class Solution {
    public List<string> findWords(char[][] board, String[] words) {
        int max = 0;
        Trie t = new Trie();
        for (String w : words) {
            t.insert(w);
        }

        int arr[][] = new int[board.length][board[0].length];
        StringBuilder str = new StringBuilder();

        Set<string> list = new HashSet();// to have only unique strings/words
        for (int i = 0; i (list);
    }

    public void traverse(int i, int j, char b[][], int arr[][], int n, int m, Trie t, StringBuilder str,Set<string> list) {

        str.append(b[i][j]);// add current cell character to form a potential prefix/word
        if (!t.startWith(str.toString())) {//early checking of prefix before moving forward to avoid un-necessary traversal
            str.deleteCharAt(str.length() - 1);
            return;
        }
        if (t.present(str.toString()))
            list.add(str.toString());

        arr[i][j] = 1;// mark current cell visited to avoid visiting the same cell the current recursive call stack

        int dirs[][] = { { 0, -1 }, { 0, 1 }, { -1, 0 }, { 1, 0 } };// left,right,up,down

        for (int dir[] : dirs) {
            int I = i + dir[0];
            int J = j + dir[1];
            if (I = 0 && J >= 0 && arr[I][J] == 0) {
                traverse(I, J, b, arr, n, m, t, str, list);
            }
        }
        arr[i][j] =0;// mark unvisited 
        str.deleteCharAt(str.length()-1);// remove the last added character
    }

}

class Node {

    Node node[] = new Node[26];
    boolean flag;

    public boolean isPresent(char c) {
        return node[c - 'a'] != null;
    }

    public Node get(char c) {
        return node[c - 'a'];
    }

    public void add(char c, Node n) {
        node[c - 'a'] = n;
    }

    public void setFlag() {
        this.flag = true;
    }

    public boolean getFlag() {
        return this.flag;
    }
}

class Trie {
    Node root;

    public Trie() {
        root = new Node();
    }

    public void insert(String s) {
        Node node = root;
        for (int i = 0; i 




          

            

            
        </string></string></string>

Das obige ist der detaillierte Inhalt vonWortsuche II. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Stellungnahme
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Wie benutze ich Maven oder Gradle für das fortschrittliche Java -Projektmanagement, die Erstellung von Automatisierung und Abhängigkeitslösung?Wie benutze ich Maven oder Gradle für das fortschrittliche Java -Projektmanagement, die Erstellung von Automatisierung und Abhängigkeitslösung?Mar 17, 2025 pm 05:46 PM

In dem Artikel werden Maven und Gradle für Java -Projektmanagement, Aufbau von Automatisierung und Abhängigkeitslösung erörtert, die ihre Ansätze und Optimierungsstrategien vergleichen.

Wie erstelle und verwende ich benutzerdefinierte Java -Bibliotheken (JAR -Dateien) mit ordnungsgemäßem Versioning und Abhängigkeitsmanagement?Wie erstelle und verwende ich benutzerdefinierte Java -Bibliotheken (JAR -Dateien) mit ordnungsgemäßem Versioning und Abhängigkeitsmanagement?Mar 17, 2025 pm 05:45 PM

In dem Artikel werden benutzerdefinierte Java -Bibliotheken (JAR -Dateien) mit ordnungsgemäßem Versioning- und Abhängigkeitsmanagement erstellt und verwendet, wobei Tools wie Maven und Gradle verwendet werden.

Wie implementiere ich mehrstufige Caching in Java-Anwendungen mit Bibliotheken wie Koffein oder Guava-Cache?Wie implementiere ich mehrstufige Caching in Java-Anwendungen mit Bibliotheken wie Koffein oder Guava-Cache?Mar 17, 2025 pm 05:44 PM

In dem Artikel wird in der Implementierung von mehrstufigem Caching in Java mithilfe von Koffein- und Guava-Cache zur Verbesserung der Anwendungsleistung erläutert. Es deckt die Einrichtungs-, Integrations- und Leistungsvorteile sowie die Bestrafung des Konfigurations- und Räumungsrichtlinienmanagements ab

Wie kann ich JPA (Java Persistence-API) für Objektrelationszuordnungen mit erweiterten Funktionen wie Caching und faulen Laden verwenden?Wie kann ich JPA (Java Persistence-API) für Objektrelationszuordnungen mit erweiterten Funktionen wie Caching und faulen Laden verwenden?Mar 17, 2025 pm 05:43 PM

In dem Artikel werden mit JPA für Objektrelationszuordnungen mit erweiterten Funktionen wie Caching und faulen Laden erläutert. Es deckt Setup, Entity -Mapping und Best Practices zur Optimierung der Leistung ab und hebt potenzielle Fallstricke hervor. [159 Charaktere]

Wie funktioniert der Klassenladungsmechanismus von Java, einschließlich verschiedener Klassenloader und deren Delegationsmodelle?Wie funktioniert der Klassenladungsmechanismus von Java, einschließlich verschiedener Klassenloader und deren Delegationsmodelle?Mar 17, 2025 pm 05:35 PM

Mit der Klassenbelastung von Java wird das Laden, Verknüpfen und Initialisieren von Klassen mithilfe eines hierarchischen Systems mit Bootstrap-, Erweiterungs- und Anwendungsklassenloadern umfasst. Das übergeordnete Delegationsmodell stellt sicher

See all articles

Heiße KI -Werkzeuge

Undresser.AI Undress

Undresser.AI Undress

KI-gestützte App zum Erstellen realistischer Aktfotos

AI Clothes Remover

AI Clothes Remover

Online-KI-Tool zum Entfernen von Kleidung aus Fotos.

Undress AI Tool

Undress AI Tool

Ausziehbilder kostenlos

Clothoff.io

Clothoff.io

KI-Kleiderentferner

AI Hentai Generator

AI Hentai Generator

Erstellen Sie kostenlos Ai Hentai.

Heißer Artikel

R.E.P.O. Energiekristalle erklärten und was sie tun (gelber Kristall)
4 Wochen vorBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Beste grafische Einstellungen
4 Wochen vorBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. So reparieren Sie Audio, wenn Sie niemanden hören können
4 Wochen vorBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Chat -Befehle und wie man sie benutzt
4 Wochen vorBy尊渡假赌尊渡假赌尊渡假赌

Heiße Werkzeuge

mPDF

mPDF

mPDF ist eine PHP-Bibliothek, die PDF-Dateien aus UTF-8-codiertem HTML generieren kann. Der ursprüngliche Autor, Ian Back, hat mPDF geschrieben, um PDF-Dateien „on the fly“ von seiner Website auszugeben und verschiedene Sprachen zu verarbeiten. Es ist langsamer und erzeugt bei der Verwendung von Unicode-Schriftarten größere Dateien als Originalskripte wie HTML2FPDF, unterstützt aber CSS-Stile usw. und verfügt über viele Verbesserungen. Unterstützt fast alle Sprachen, einschließlich RTL (Arabisch und Hebräisch) und CJK (Chinesisch, Japanisch und Koreanisch). Unterstützt verschachtelte Elemente auf Blockebene (wie P, DIV),

Herunterladen der Mac-Version des Atom-Editors

Herunterladen der Mac-Version des Atom-Editors

Der beliebteste Open-Source-Editor

EditPlus chinesische Crack-Version

EditPlus chinesische Crack-Version

Geringe Größe, Syntaxhervorhebung, unterstützt keine Code-Eingabeaufforderungsfunktion

PHPStorm Mac-Version

PHPStorm Mac-Version

Das neueste (2018.2.1) professionelle, integrierte PHP-Entwicklungstool

WebStorm-Mac-Version

WebStorm-Mac-Version

Nützliche JavaScript-Entwicklungstools