Obtenir une liste de mots d'une trie

Vous devez traverser le sous-arbre à partir du noeud que vous avez trouvé pour le préfixe.

Démarrer de la même manière, c'est-à-dire trouver le bon nœud. Ensuite, au lieu de vérifier son marqueur, traverser cet arbre (c'est-à-dire aller sur tous ses descendants; un DFS < / a> est un bon moyen de le faire), sauvegarder la sous-chaîne utilisée pour atteindre le nœud "actuel" à partir du premier nœud.

Si le nœud actuel est marqué comme un mot, sortie * Le préfixe + la sous-chaîne atteinte.

* ou ajoutez-le à une liste ou quelque chose.

J'ai construit une trie une fois pour l'une des ITA Puzzles

public class WordTree {


class Node {

    private final char ch;

    /**
     * Flag indicates that this node is the end of the string.
     */
    private boolean end;

    private LinkedList<Node> children;

    public Node(char ch) {
        this.ch = ch;
    }

    public void addChild(Node node) {
        if (children == null) {
            children = new LinkedList<Node>();
        }
        children.add(node);
    }

    public Node getNode(char ch) {
        if (children == null) {
            return null;
        }
        for (Node child : children) {
            if (child.getChar() == ch) {
                return child;
            }
        }
        return null;
    }

    public char getChar() {
        return ch;
    }

    public List<Node> getChildren() {
        if (this.children == null) {
            return Collections.emptyList();
        }
        return children;
    }

    public boolean isEnd() {
        return end;
    }

    public void setEnd(boolean end) {
        this.end = end;
    }
}


Node root = new Node(' ');

public WordTree() {
}

/**
 * Searches for a strings that match the prefix.
 *
 * @param prefix - prefix
 * @return - list of strings that match the prefix, or empty list of no matches are found.
 */
public List<String> getWordsForPrefix(String prefix) {
    if (prefix.length() == 0) {
        return Collections.emptyList();
    }
    Node node = getNodeForPrefix(root, prefix);
    if (node == null) {
        return Collections.emptyList();
    }
    List<LinkedList<Character>> chars = collectChars(node);
    List<String> words = new ArrayList<String>(chars.size());
    for (LinkedList<Character> charList : chars) {
        words.add(combine(prefix.substring(0, prefix.length() - 1), charList));
    }
    return words;
}


private String combine(String prefix, List<Character> charList) {
    StringBuilder sb = new StringBuilder(prefix);
    for (Character character : charList) {
        sb.append(character);
    }
    return sb.toString();
}


private Node getNodeForPrefix(Node node, String prefix) {
    if (prefix.length() == 0) {
        return node;
    }
    Node next = node.getNode(prefix.charAt(0));
    if (next == null) {
        return null;
    }
    return getNodeForPrefix(next, prefix.substring(1, prefix.length()));
}


private List<LinkedList<Character>> collectChars(Node node) {
    List<LinkedList<Character>> chars = new ArrayList<LinkedList<Character>>();

    if (node.getChildren().size() == 0) {
        chars.add(new LinkedList<Character>(Collections.singletonList(node.getChar())));
    } else {
        if (node.isEnd()) {
            chars.add(new LinkedList<Character> 
            Collections.singletonList(node.getChar())));
        }
        List<Node> children = node.getChildren();
        for (Node child : children) {
            List<LinkedList<Character>> childList = collectChars(child);
            for (LinkedList<Character> characters : childList) {
                characters.push(node.getChar());
                chars.add(characters);
            }
        }
    }
    return chars;
}


public void addWord(String word) {
    addWord(root, word);
}

private void addWord(Node parent, String word) {
    if (word.trim().length() == 0) {
        return;
    }
    Node child = parent.getNode(word.charAt(0));
    if (child == null) {
        child = new Node(word.charAt(0));
        parent.addChild(child);
    } if (word.length() == 1) {
        child.setEnd(true);
    } else {
        addWord(child, word.substring(1, word.length()));
    }
}


public static void main(String[] args) {
    WordTree tree = new WordTree();
    tree.addWord("world");
    tree.addWord("work");
    tree.addWord("wolf");
    tree.addWord("life");
    tree.addWord("love");
    System.out.println(tree.getWordsForPrefix("wo"));
}

Voici une implémentation en C ++

https://github.com/dcharvezlive/basic-trie

Dans votre fonction de recherche, vous pouvez le renvoyer le nœud d'où se termine le préfixe. Si vous vous assurez que votre nœud a un champ pour sauver chaque enfant (vecteur?), Vous pouvez répertorier tous les enfants de ce nœud où votre préfixe se termine.

J'ai fait face à ce problème tout en essayant de créer un module de texte automatique. J'ai résolu le problème en faisant une trie dans laquelle chaque nœud contient son nœud parent ainsi que des enfants. D'abord, j'ai recherché le noeud à partir du préfixe d'entrée. Ensuite, j'ai appliqué une traversée sur la trépille qui explore tous les nœuds du sous-arbre avec sa racine comme noeud de préfixe. Chaque fois qu'un nœud de feuille est rencontré, cela signifie que la fin d'un mot à partir du préfixe d'entrée a été trouvée. À partir de ce nœud de la feuille I Itérale à travers les nœuds parents obtenus parent de parents et atteignez la racine du sous-arbre. Tout comme cela, j'ai continué à ajouter les clés des nœuds dans une pile. En fin de compte, j'ai pris le préfixe et j'ai commencé l'annexé en faisant apparaître la pile. J'ai continué à sauver les mots dans une arrayliste. À la fin de la traversée, je reçois tous les mots à partir du préfixe d'entrée. Voici le code avec l'exemple d'utilisation: xxx

- xxx

exemple xxx

Après la construction de Trie, vous pouvez faire des dfs à partir du nœud, où vous avez trouvé préfixe: xxx

Le code reconsive ci-dessous peut être utilisé lorsque votre triende est comme ceci: Ce code fonctionne bien.

TrieNode(char c)
{

        this.con=c;
        this.isEnd=false;
        list=new ArrayList<TrieNode>();
        count=0;

}

//--------------------------------------------------

public void Print(TrieNode root1, ArrayList<Character> path)
{

      if(root1==null)
          return;

      if(root1.isEnd==true)
      {
          //print the entire path
          ListIterator<Character> itr1=path.listIterator();
          while(itr1.hasNext())
          {
              System.out.print(itr1.next());
          }
          System.out.println();
          return;
      }
      else{
          ListIterator<TrieNode> itr=root1.list.listIterator();
          while(itr.hasNext())
          {
              TrieNode child=itr.next();
              path.add(child.con);
              Print(child,path);
              path.remove(path.size()-1);

            }
      }

Un algorithme DFS récursif simple peut être utilisé pour trouver tous les mots pour un préfixe donné.

échantillon Node Trie: P>

static List<String> findAllWordsForPrefix(String prefix, TrieNode root) {
    List<String> words = new ArrayList<>();
    TrieNode current = root;
    for(Character c: prefix.toCharArray()) {
        TrieNode nextNode = current.children.get(c);
        if(nextNode == null) return words;
        current = nextNode;
    }
    if(!current.children.isEmpty()) {
        findAllWordsForPrefixRecursively(prefix, current, words);
    } else {
        if(current.isWord) words.add(prefix);
    }
    return words;
}

static void findAllWordsForPrefixRecursively(String prefix, TrieNode node, List<String> words) {
    if(node.isWord) words.add(prefix);
    if(node.children.isEmpty()) {
        return;
    }
    for(Character c: node.children.keySet()) {
        findAllWordsForPrefixRecursively(prefix + c, node.children.get(c), words);
    }
}