Trie Umsetzung

Question

Ich versuche, eine sehr einfache Trie in Java zu implementieren, die drei Operationen unterstützt. Ich möchte es eine Insert-Methode haben, ein Verfahren hat (dh ein bestimmtes Wort in der Trie) und eine Methode toString die Trie in String-Form zurückzukehren. Ich glaube, ich habe Einfügung ordnungsgemäß funktioniert, hat aber und toString erweisen sich als schwierig. Hier ist, was ich habe so weit.

Die Trie-Klasse.

public class CaseInsensitiveTrie implements SimpleTrie {

    //root node
    private TrieNode r;

    public CaseInsensitiveTrie() {
        r = new TrieNode();
    }

    public boolean has(String word) throws InvalidArgumentUosException {
        return r.has(word);
    }

    public void insert(String word) throws InvalidArgumentUosException {
        r.insert(word);
    }

    public String toString() {
        return r.toString();
    }

    public static void main(String[] args) {

        CaseInsensitiveTrie t = new CaseInsensitiveTrie();

        System.out.println("Testing some strings");
        t.insert("TEST");
        t.insert("TATTER");
        System.out.println(t.has("TEST"));
    }
}

Und die Knotenklasse

public class TrieNode {

    //make child nodes
    private TrieNode[] c;
    //flag for end of word
    private boolean flag = false;

    public TrieNode() {
        c = new TrieNode[26]; //1 for each letter in alphabet
    }

    protected void insert(String word) {
        int val = word.charAt(0) - 64;

        //if the value of the child node at val is null, make a new node
                //there to represent the letter
        if (c[val] == null) {
            c[val] = new TrieNode();
        }

        //if word length > 1, then word is not finished being added.
        //otherwise, set the flag to true so we know a word ends there.
        if (word.length() > 1) {
            c[val].insert(word.substring(1));
        } else {
            c[val].flag = true;
        }
    }

    public boolean has(String word) {
        int val = word.charAt(0) - 64;
        if (c[val]!=null && word.length()>1) {
            c[val].has(word.substring(1));
        } else if (c[val].flag==true && word.length()==1) {
            return true;
        }

        return false;
    }

    public String toString() { 
        return "";
    }
}

Also im Grunde, wenn ein Trie zu schaffen, wird ein TrieNode als Wurzel mit 26 Kindern erstellt. Wenn ein Einfügen versucht wird, ist durch Umspritzen auf diesem Wurzelknoten genannt wird, die rekursiv einen neuen Knoten in der korrekten Position schafft, und fährt fort, bis das Wort abgeschlossen ist. Ich glaube, dass Verfahren ordnungsgemäß funktioniert.

Meine hat Funktion sehr gebrochen, weil ich wurde , dass return-Anweisung haben, außerhalb der Klammern aus irgendeinem Grund. Ich kann es nicht innerhalb einer else-Klausel enthalten, oder der Compiler beschwert. Other than that, ich denke, dass Verfahren mit einigen Optimierungen funktionieren sollen, aber ich kann es nicht für das Leben von mir herauszufinden.

toString ist ein Tier habe ich versucht, in Angriff zu nehmen, aber nichts, was ich an ihn werfen funktioniert, also werde ich das verlassen, bis ich das hat Problem zu lösen. Wenn ich hat bekommen arbeiten ich einen Weg, der Lage sein, auf Figur kann es in eine toString Funktion zu formatieren.

Der Zweck der int val = word.charAt (0) - 64; Denn jede Zeichenfolge eingegeben müssen alle Kappen (diese danach will ich schaffen eine String-Funktion, um sicherzustellen, Formatierung) sein, damit der int-Wert des ersten Buchstaben - 64 wird es in der Feldposition sein. dh Array-Index 0 ein, so A = 64, A - 64 = 0 B = 65, B -. 64 = 1, und so weiter

Answer 1

Ihre has Funktion sollte wohl so aussehen:

if (c[val]!=null && word.length()>1) {
    return c[val].has(word.substring(1)); //<-- Change is on this line
} else if (c[val].flag==true && word.length()==1) {
    ...etc

Sie führen den rekursiven Aufruf, aber Sie müssen wirklich Wert lassen, um den ursprünglichen Anrufer propagieren zurück.

Answer 2

Vielleicht können Sie nur verwenden „Karte c“ anstelle von „TrieNode [] c“, die Sie dies für alle Arten von Zeichen Groß- / Kleinschreibung und auch Sonderzeichen zu verwenden, erlauben würde, und auch Sie Platz sparen würde (26 Zuteilen Zeichenfeld zu jeder Zeichenebene)

Answer 3

Hier ist meine Implementierung: -

public class Tries {

class Node {
    HashMap<Character, Node> children;
    boolean end;
    public Node(boolean b){
        children = new HashMap<Character, Tries.Node>();
        end = false;
    }
}
private Node root;
public Tries(){
    root = new Node(false);
}
public static void main(String args[]){
    Tries tr = new Tries();
    tr.add("dog");
    tr.add("doggy");

    System.out.println(tr.search("dogg"));
    System.out.println(tr.search("doggy"));
}
private boolean search(String word) {
    Node crawl = root;
    int n = word.length();
    for(int i=0;i<n;i++){
        char ch = word.charAt(i);
        if(crawl.children.get(ch) == null){
            return false;
        }
        else {
            crawl = crawl.children.get(ch);
            if(i==n-1 && crawl.end == true){
                return true;
            }

        }
    }
    return false;
}
private void add(String word) {
    Node crawl = root;
    int n = word.length();
    for(int i=0;i<n;i++){
        char ch = word.charAt(i);
        if(crawl.children.containsKey(ch)){
            crawl = crawl.children.get(ch);
        }
        else {
            crawl.children.put(ch, new Node(false));
            Node temp = crawl.children.get(ch);
            if(i == n-1){
                temp.end = true;
            }
            crawl = temp;
            System.out.println(ch + "      " + crawl.end);

        }
    }
}

}

Answer 4

Hier ist meine Implementierung:

public class Tries {
private static class Leaf {
    private Leaf(char c) {
        this.c=c;
    }
    char c;
    int counter = 1;
    List<Leaf> leaves = new ArrayList<>(10);
}
private Leaf root = new Leaf('0');
public void add(String word) {
    Leaf current = root;
    Leaf newLeaf = null;
    for (char c : word.toCharArray()) {
        boolean found = false;
        for (Leaf leaf : current.leaves) {
            if (leaf.c == c) {
                current = leaf;
                current.counter++;
                found=true;
                break;
            }
        }
        if (!found) {
            newLeaf = new Leaf(c);
            current.leaves.add(newLeaf);
            current = newLeaf;
        }
    }
}
public int find(String partial) {
    Leaf current = root;
    for (char c : partial.toCharArray()) {
        boolean found = false;
        for (Leaf leaf : current.leaves) {
            if (leaf.c == c) {
                current=leaf;
                found=true;
                break;
            }
        }
        if(!found) return 0;
    }
    return current.counter;
}

public boolean hasWord(String partial) {
    return find(partial)>0;
    }
}

Answer 5

Diese Trie Karte Arbeitsgeräte has (genannt get in dieser Implementierung) und toString

Answer 6

Hier ist einfache Java-Implementierung ohne andere Datenstruktur mit

import java.util.ArrayList;
import java.util.List;

class Trie {

    private static Node root = new Node(' ', false);

    static int getIndex(char x) {
        return ((int) x) - ((int) 'a');
    }

    static class Node {
        char data;
        boolean isLeaf;
        Node[] children;

        Node(char data, boolean leaf) {
            this.data = data;
            this.isLeaf = leaf;
            this.children = new Node[26];
        }

    }

    static void insert(String data, Node root) {
        if (data == null || data.length() == 0) {
            return;
        }
        Node child = root.children[getIndex(data.charAt(0))];
        if (child == null) {
            Node node = new Node(data.charAt(0), data.length() == 1);
            root.children[getIndex(data.charAt(0))] = node;
            if (data.length() > 1) {
                insert(data.substring(1, data.length()), node);
            }
        } else {
            if (data.length() == 1) {
                child.isLeaf = true;
            } else {
                insert(data.substring(1, data.length()), child);
            }
        }
    }

    static boolean find(String data, Node root) {
        if (data == null || data.length() == 0) {
            return true;
        }
        char x = data.charAt(0);
        //note that first node ie root is just dummy, it just holds important
        Node node = root.children[getIndex(x)];
        if (node == null) {
            return false;
        } else {
            if (data.length() == 1) {
                return node.isLeaf;
            } else {
                return find(data.substring(1, data.length()), node);
            }
        }
    }

    static boolean delete(String data, Node root) {
        if (data == null || data.length() == 0) {
            return false;
        }
        char x = data.charAt(0);
        //note that first node ie root is just dummy, it just holds important
        Node node = root.children[getIndex(x)];
        if (node == null) {
            return false;
        } else {
            if (data.length() == 1) {
                node.isLeaf = false;
                boolean allNull = true;
                for (Node node1 : node.children) {
                    allNull = allNull && node1 == null;
                }
                return allNull;
            } else {
                boolean delete = delete(data.substring(1, data.length()), node);
                if (delete) {
                    node.children[getIndex(x)] = null;
                    if(node.isLeaf){
                        return false;
                    }
                    boolean allNull = true;
                    for (Node node1 : node.children) {
                        allNull = allNull && node1 == null;
                    }
                    return allNull;                }
            }
        }
        return false;
    }


    private static List<String> strings = new ArrayList<>();

    private static List<String> getAll() {
        strings = new ArrayList<String>();
        findAllDFS(root, "");
        return strings;
    }

    private static void findAllDFS(Node node, String old) {
        if (node != null) {
            if (node.data != ' ') {
                old = old + node.data;
            }
            if (node.isLeaf) {
                strings.add(old);
            }
            for (Node node1 : node.children) {
                findAllDFS(node1, old);
            }
        }
    }

    public static void main(String[] args) {
        insert("abc", root);
        insert("xyz", root);
        insert("abcd", root);
        insert("abcde", root);


        delete("abcd", root);

 /*       System.out.println(find("abc", root));
        System.out.println(find("abcd", root));
        System.out.println(find("ab", root));
        System.out.println(find("xyz", root));*/


        System.out.println(getAll());
    }


}