Java实现基于Trie树结构的回文前缀树

Trie树（也称为前缀树）是一种用于存储字符串的树形结构

import java.util.HashMap;
import java.util.Map;

class TrieNode {
    Map<Character, TrieNode> children;
    boolean isEndOfWord;

    public TrieNode() {
        children = new HashMap<>();
        isEndOfWord = false;
    }
}

public class PalindromeTrie {
    private TrieNode root;

    public PalindromeTrie() {
        root = new TrieNode();
    }

    // 插入一个字符串到回文前缀树中
    public void insert(String word) {
        TrieNode current = root;
        for (char ch : word.toCharArray()) {
            current.children.putIfAbsent(ch, new TrieNode());
            current = current.children.get(ch);
        }
        current.isEndOfWord = true;
    }

    // 检查回文前缀树中是否存在某个字符串
    public boolean search(String word) {
        TrieNode current = root;
        for (char ch : word.toCharArray()) {
            if (!current.children.containsKey(ch)) {
                return false;
            }
            current = current.children.get(ch);
        }
        return current.isEndOfWord;
    }

    // 检查回文前缀树中是否存在某个字符串的前缀
    public boolean startsWith(String prefix) {
        TrieNode current = root;
        for (char ch : prefix.toCharArray()) {
            if (!current.children.containsKey(ch)) {
                return false;
            }
            current = current.children.get(ch);
        }
        return true;
    }

    public static void main(String[] args) {
        PalindromeTrie trie = new PalindromeTrie();
        trie.insert("madam");
        trie.insert("hello");
        trie.insert("world");

        System.out.println(trie.search("madam")); // 输出: true
        System.out.println(trie.search("hello")); // 输出: true
        System.out.println(trie.search("world")); // 输出: true
        System.out.println(trie.search("hell")); // 输出: false

        System.out.println(trie.startsWith("mad")); // 输出: true
        System.out.println(trie.startsWith("hel")); // 输出: true
        System.out.println(trie.startsWith("wor")); // 输出: true
        System.out.println(trie.startsWith("worl")); // 输出: false
    }
}

这个实现中，我们定义了一个TrieNode类来表示回文前缀树的节点，每个节点包含一个字符到子节点的映射（children）和一个布尔值（isEndOfWord），表示该节点是否是一个字符串的结尾。

PalindromeTrie类包含一个根节点（root），以及插入、搜索和前缀检查的方法。插入方法将一个字符串的每个字符按顺序插入到回文前缀树中；搜索方法检查回文前缀树中是否存在某个字符串；前缀检查方法检查回文前缀树中是否存在某个字符串的前缀。