使用两次尝试实现电话目录

Question

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

我想通过尝试来解决它。通过尝试解决问题，我尝试使用两次尝试，一次用于姓名，另一次用于电话号码，但我遇到了困难
假设，我必须添加三个条目(AB"112"BC"124"CD"225"(然后，如果我查询号码"225"的名称，我该如何返回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，所以我不能在你的代码中发表评论。

使用trys的想法是有效的。

你似乎错过了节点在尝试时可以保存的数据

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

1. 它所拥有的数据可以是任何类型
2. 子项列表(或左、右子项(或任何子项组合

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

所以trie节点看起来像这个

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

因此，对于正向查找(名称到电话(，您可以构造一个Trie，并在与目录中条目匹配的节点上将Value设置为该条目。

你需要创建第二个trie来进行反向查找(电话到名称(

因此，给你一个例子，对于这些数据，它将是

(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，当你到达一个节点并想要检查值时，只需读取值

我希望是清楚的