使用两次尝试实现 phone 目录

Question

    I have encountered an interview question
    “Implement a phone directory using Data Structures”

我想用 tries.By 尝试解决它，我尝试了两次尝试，一次用于名称，另一次用于 phone 号码，但是我遇到了困难。
假设，我必须添加三个条目（AB “112” BC “124” CD “225”）那么如果我查询号码“225”的名称，我如何return CD。也就是说，这两个尝试将如何链接。

    One approach I was thinking was taking two pointers in both the tries.
    These pointers will point to the first and last word in the other trie.
    For example,if the structures are as follows:

    Struct nametrie                            
    {                                                       
     Struct nametrie *child[26];
     struct phonetrie*head,*tail;
     struct phonetrie*root;       

     -----------    
    }                                                       

      Struct phonetrie
     {
             struct phonetrie*child[9];
             struct nametrie*head,*tail;
             struct nametrie*root;
        ----------- 
      }


    Then for AB “112”,  
    Name trie willstore head(1) and tail (2).

但我认为这种方法不适用于重复条目（一个名字和多个数字。）

Can someone please explain a good approach.I am not looking for code but good understanding of approach,may be via diagram or algorithm.

Answer 1

我不懂 C，所以无法在您的代码中发表评论。

使用尝试的想法是有效的。

您似乎遗漏了节点在尝试中可以保存的数据

树中的节点有 2 个主要组件

它拥有的数据可以是任何类型
子项列表（或左、右子项）或子项的任意组合

我们在这里要做的是，我们将为每个节点添加另一个字段并将其称为值"theValue"

所以 trie 节点将如下所示

Class TrieNode{
public char theChar;
public String theValue;
public List<TrieNode> children;
}

因此，对于正向查找（名称为 phone），您构建一个 Trie 并在与目录中的条目匹配的节点上将 theValue 设置为该条目。

您将需要创建第二个 trie 来为反向查找执行相同的操作（phone 命名）

所以给你举个例子，这个数据会是什么样子

( AB “112” AC “124” ACD “225”)

//create nodes
TrieNode root = new TrieNode();
TrieNode A = new TrieNode();
A.theChar = 'A';
TrieNode B = new TrieNode();
A.theChar = 'B';
TrieNode C = new TrieNode();
A.theChar = 'C';
TrieNode C2 = new TrieNode();
A.theChar = 'C';
TrieNode D = new TrieNode();
A.theChar = 'D';
//link nodes together
root.children = new ArrayList<>();
root.children.add(A);
A.children = new ArrayList<>();
A.children.add(B);
A.children.add(C);
B.children = new ArrayList<>();
B.children.add(C2);
//fill the data
B.theValue = "112";
C.theValue = "124";
C2.theValue = "225";

现在您可以轻松遍历这个 Trie，当您到达一个节点并想检查值时，只需读取 theValue

我希望清楚

使用两次尝试实现 phone 目录

Implement phone directory using two tries

string

algorithm

trie