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

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，所以我不能评论你的代码。

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

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

树中的节点有两个主要部分

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

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

所以trie节点会是这样的

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

因此，对于正向查找(姓名到电话)，您构建一个 Trie 树，并在与目录中的条目匹配的节点上将 theValue 设置为该条目。

您将需要创建第二个尝试以对反向查找(电话到姓名)执行相同的操作

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

(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

我希望这是清楚的