DFS sur chaîne Trie (préfixe)

Question

I écrit le préfixe suivant Trie:

class TrieNode { 
    char letter; 
    HashMap<Character,TrieNode> children; 
    boolean fullWord; 

    TrieNode(char letter) { 
     this.letter = letter; 
     children = new HashMap<Character, TrieNode>(); 
     this.fullWord = false; 
    } 
} 

class Tree{ 
    static TrieNode createTree() { 
     return (new TrieNode('\0')); 
    } 

    static void insertWord(TrieNode root, String word) { 
     int l = word.length(); 
     char[] letters = word.toCharArray(); 
     TrieNode curNode = root; 
     for (int i = 0; i < l; i++) { 
      if (!curNode.children.containsKey(letters[i])) 
       curNode.children.put(letters[i], new TrieNode(letters[i])); 
      curNode = curNode.children.get(letters[i]); 
     } 
     curNode.fullWord = true; 
    } 
} 

Je voudrais ajouter la méthode DFS afin de trouver le premier nœud qui a plus de 1 enfant (donc il va me montrer le préfixe commun le plus long).

J'ai écrit ce code:

static void DFS(TrieNode node) { 
    for (TrieNode tn: node.children.values()){ 
     DFS(tn); 
     if (node.children.size()>2) 
     System.out.println("found the first vertex"); 
    } 
} 

Mais il ne fonctionne pas. Qu'est-ce que je fais mal?

Answer 1

Eh bien, nous devons d'abord préciser que commun le plus long préfixe signifie ici le préfixe commun le plus long de deux ou plusieurs chaînes dans l'arbre trie.

Ainsi, votre méthode DFS ne pas fonctionner correctement car il traverse simplement l'arbre entier et la volonté sortie « trouvé le premier sommet » sur la visite un nœud dont children.size()> 2 (Il devrait être> = 2 ici)

Ce que nous voulons ici est de trouver le seul préfixe commun le plus long . Nous avons donc besoin d'informations supplémentaires sur la plus longue. Il est facile de voir que dans mon exemple ci-dessus:

  root  --depth: 0 
      | 
      a  --depth: 1 
      | 
      b  --depth: 2 
     /\ 
     c f  --depth: 3 
     /|\ 
     d g k  --depth: 4 
      \ 
      k  --depth: 5 

Le plus long noeud préfixe commun a children.size()> 1 ET a une profondeur max.Dans ce cas, il est noeud c

Voici donc un possible DFS correct:

static int max=-1; 
static TrieNode maxNode=null; 

static void dfs(TrieNode node, int depth){ 
    if(node.children.size()>1 && depth>max){ 
     max=depth; 
     maxNode=node; 
    } 
    for (TrieNode tn: node.children.values()) 
     dfs(tn,depth+1); 
} 

public static void test(){ 
    TrieNode root = Tree.createTree(); 
    Tree.insertWord(root, "abcd"); 
    Tree.insertWord(root, "abcg"); 
    Tree.insertWord(root, "abckk"); 
    Tree.insertWord(root, "abf"); 
    dfs(root,0); 
    System.out.println("Max node:"+maxNode.letter); 
} 

Après l'exécution de DSF, le maxnode tiendra le nœud qui arrête le préfixe commun le plus long. c'est le noeud c dans ce cas.

Answer 2

Votre code d'arborescence de préfixe semble bon. Au moins, c'est logique pour moi mais je n'ai pas vérifié tous les cas de coin. Le problème est votre méthode DFS. En supposant que nous avons les chaînes suivantes qui se composent de votre arbre préfixe:

- "abcd" 
- "abcg" 
- "abckk" 
- "abf" 

Ainsi l'arbre préfixe devrait ressembler à ceci:

   root 
       | 
       a 
       | 
       b 
      /\ 
      c f 
      /|\ 
      d g k 
       \ 
       k 

Je pense que ce que vous attendez est que nous pouvons produire le "trouvé le premier sommet "au noeud b (car, évidemment," ab "est le plus long préfixe commun des quatre chaînes ci-dessus), cependant, votre DFS ne fonctionne pas de cette façon. Il ira sur le chemin

root->a->b->c->d then back to c, finding that c.children.size() >1 , then output. 

Notez que "2 ou plus" est> = 2 ou> 1 qui dans votre programme est> 2. Je pensais que ça devrait être une faute de frappe. Pour corriger votre DFS, il suffit de le modifier pour vérifier les enfants d'un nœud taille première fonctionnera:

static boolean DFS(TrieNode node) { 
    if (node.children.size()>1){ 
     System.out.println("found the first vertex on node:"+node.letter); 
     return true; 
    } 
    for (TrieNode tn: node.children.values()){ 
     if(DFS(tn)) 
      return true; 
    } 
    return false; 
} 

Note pour faire l'arrêt du programme sur la recherche de notre nœud, je modifie le type de retour de vous DFS. En outre, en ce qui concerne sur la recherche de plus long préfixe commun, DFS ne peut pas être un meilleur choix ici, le code suivant est mieux que DFS en termes de complexité d'exécution:

static void lcp(TrieNode node){ 
    TrieNode first = node; 
    while(first.children.size()==1) 
     first = first.children.values().iterator().next(); 
    System.out.println("found the first vertex on node:"+first.letter); 
}