Java实现基于字典树的回文串检测

在Java中，我们可以使用字典树（Trie）数据结构来实现基于字典树的回文串检测

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEndOfWord = false;
}

public class PalindromeChecker {
    private TrieNode root;

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

    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.isEndOfWord = true;
    }

    public boolean isPalindrome(String word) {
        TrieNode node = search(word);
        return isPalindromeHelper(node, 0, word.length() - 1);
    }

    private TrieNode search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                return null;
            }
            node = node.children[index];
        }
        return node;
    }

    private boolean isPalindromeHelper(TrieNode node, int start, int end) {
        if (start >= end) {
            return true;
        }
        if (node.isEndOfWord) {
            return isPalindromeHelper(root, start + 1, end - 1);
        }
        if (node.children[0] != null && node.children[0].isEndOfWord) {
            return isPalindromeHelper(node.children[0], start, end - 1);
        }
        if (node.children[1] != null && node.children[1].isEndOfWord) {
            return isPalindromeHelper(node.children[1], start + 1, end);
        }
        return false;
    }

    public static void main(String[] args) {
        PalindromeChecker checker = new PalindromeChecker();
        checker.insert("ababa");
        System.out.println(checker.isPalindrome("ababa")); // 输出: true
        System.out.println(checker.isPalindrome("abcba")); // 输出: true
        System.out.println(checker.isPalindrome("hello")); // 输出: false
    }
}

在这个实现中，我们首先创建了一个TrieNode类来表示字典树的节点。然后，我们创建了一个PalindromeChecker类，其中包含一个字典树的根节点以及插入和检测回文串的方法。

insert方法用于将单词插入字典树。isPalindrome方法首先使用search方法找到给定单词的最后一个字符对应的节点，然后调用isPalindromeHelper方法递归地检查从两端到中间的所有字符是否形成回文串。

isPalindromeHelper方法是一个递归方法，它检查从给定节点开始的两端字符是否形成回文串。如果遇到以元音结尾的单词，它会跳过该元音字符。如果所有字符都形成回文串，则返回true，否则返回false。