前缀树.md

前缀树

前缀树实现

• Code_0030_TrieTree.java

• LeetCode_0208_Trie.java

---

单词拆分 I

• LintCode_0107_WordBreak.java 只能通过前缀树优化才能AC

• LeetCode_0139_WordBreak.java

单词拆分 II

• LeetCode_0140_WordBreakII.java

最大异或和的子数组

• NowCoder_MaxXorSubArray.java

tips: 方法1：暴力解O(N^3) 方法2：O(N^2) 前缀异或和 辅助数组 方法3：前缀树 [11,1,15,10,13,4] e[-1] = 0000 e[0..0] = 11 = 1011 e[0..1] = 11^1 = 1010 e[0..2] = 0101 e[0..3] = 1111 e[0..4] = 0010 e[0..5] = 0110 这些数构造成前缀树 最高位（符合位）期待一样，紧着高位要期待不一样的