Trie树 POJ 1056

短命女 2022-09-30 00:53 150阅读 0赞

Trie树提供给了一种能够在字符串的长度n时间内判断出来是否在已有集合中已经存在这个字符串了。

1056是判断前缀码的问题。如果所有字符串都不是其他的字符串的前缀的话，那么就是可以直接编码的。

java代码如下：

其中TrieTree类提供了一种建立字典树的方法。在字典树的建立过程中，可以同时求出是否已经存在该字符串。

代码中注释的比较清楚了。

import java.util.Scanner; public class Main \{ public static void main(String ars\[\]) \{ int count = 0; // File file = new File("D://test.txt"); Scanner cin = new Scanner(System.in); String bin = cin.nextLine(); while (true) \{ count++; TrieTree tree = new TrieTree(); boolean flag = true; boolean print = false; while (!bin.equals("9")) \{ if (flag) flag = tree.addWord(bin); if (!flag && !print) \{// 如果是前缀，输出no System.out.println("Set " + count + " is not immediately decodable"); flag = false; print = true; \} bin = cin.nextLine(); \} if (flag) \{// 如果不是前缀，输出yes System.out .println("Set " + count + " is immediately decodable"); \} // 下一组测试 bin = cin.nextLine(); \} \} \} class TrieTree \{ private Vertex root;// 一个Trie树有一个根节点 // 内部类 protected class Vertex \{// 节点类 protected Vertex\[\] edges;// 每个节点包含10个子节点(类型为自身) boolean isEnd;// 说明是不是一个字符串的末尾 Vertex() \{ isEnd = false; edges = new Vertex\[10\]; for (int i = 0; i < edges.length; i++) \{ edges\[i\] = null; \} \} \} public TrieTree() \{ root = new Vertex(); \} public boolean addWord(String word) \{ if (word.length() == 1) return addWord(root, word, true); else return addWord(root, word, false); \} // last标记word是不是新加入的字符串的最后一位，true为是最后一位，false为不是最后一位 private boolean addWord(Vertex vertex, String word, boolean last) \{ int index = Integer.parseInt(word.charAt(0) + ""); if (last) \{ // 如果是新字符串的最后一个元素，则设置为isEnd为true if (vertex.edges\[index\] == null) \{ // if the edge does NOT exist vertex.edges\[index\] = new Vertex(); \} else \{ // 是新字符串的最后一个数据，但是该元素在trie树中已经存在，则肯定return false return false; \} vertex.edges\[index\].isEnd = true;// 如果是最后一个元素，但是trie树中还没有该数据，设置为true return true; \} else \{ if (vertex.edges\[index\] == null) \{ // if the edge does NOT exist vertex.edges\[index\] = new Vertex(); \} if (vertex.edges\[index\].isEnd) // 如果找到了一个电话号码是前缀，输出no return false; if (word.length() == 2) return addWord(vertex.edges\[index\], word.substring(1), true); // 下一个字符 else return addWord(vertex.edges\[index\], word.substring(1), false); // 下一个字符 \} \} \}