@Test public void randomTest() { int N = 100; Random r = new Random(); for (int i = 0; i <= 800; i++) { if (i % 100 == 99) N <<= 1; List<Integer> pre = Shuffler.getRandomList(1 + r.nextInt(N), 0, N); List<String> input = pre.stream().map((a) -> Integer.toBinaryString(a)).collect(Collectors.toList()); String[] cur = input.toArray(new String[0]); Assert.assertEquals(expect(cur.clone()), PrefixFreeCode.isPrefixFree(cur)); } }
public static boolean isPrefixFree(String[] input) { TrieNode root = new TrieNode(); for (String s : input) { TrieNode p = root; char[] cur = s.toCharArray(); for (int i = 0; i < cur.length; i++) { int key = cur[i] - '0'; if (p.chds[key] == null) { p.chds[key] = new TrieNode(); } p = p.chds[key]; if (p.isEnd) return false; } p.isEnd = true; if (p.chds[0] != null || p.chds[1] != null) return false; } return true; }
PrefixFreeCode { public static boolean isPrefixFree(String[] input) { TrieNode root = new TrieNode(); for (String s : input) { TrieNode p = root; char[] cur = s.toCharArray(); for (int i = 0; i < cur.length; i++) { int key = cur[i] - '0'; if (p.chds[key] == null) { p.chds[key] = new TrieNode(); } p = p.chds[key]; if (p.isEnd) return false; } p.isEnd = true; if (p.chds[0] != null || p.chds[1] != null) return false; } return true; } }
PrefixFreeCode { public static boolean isPrefixFree(String[] input) { TrieNode root = new TrieNode(); for (String s : input) { TrieNode p = root; char[] cur = s.toCharArray(); for (int i = 0; i < cur.length; i++) { int key = cur[i] - '0'; if (p.chds[key] == null) { p.chds[key] = new TrieNode(); } p = p.chds[key]; if (p.isEnd) return false; } p.isEnd = true; if (p.chds[0] != null || p.chds[1] != null) return false; } return true; }  }
PrefixFreeCode { public static boolean isPrefixFree(String[] input) { TrieNode root = new TrieNode(); for (String s : input) { TrieNode p = root; char[] cur = s.toCharArray(); for (int i = 0; i < cur.length; i++) { int key = cur[i] - '0'; if (p.chds[key] == null) { p.chds[key] = new TrieNode(); } p = p.chds[key]; if (p.isEnd) return false; } p.isEnd = true; if (p.chds[0] != null || p.chds[1] != null) return false; } return true; }  static boolean isPrefixFree(String[] input); }
PrefixFreeCode { public static boolean isPrefixFree(String[] input) { TrieNode root = new TrieNode(); for (String s : input) { TrieNode p = root; char[] cur = s.toCharArray(); for (int i = 0; i < cur.length; i++) { int key = cur[i] - '0'; if (p.chds[key] == null) { p.chds[key] = new TrieNode(); } p = p.chds[key]; if (p.isEnd) return false; } p.isEnd = true; if (p.chds[0] != null || p.chds[1] != null) return false; } return true; }  static boolean isPrefixFree(String[] input);  }