Java實現(xiàn)基于字典樹的回文串檢測

在Java中，我們可以使用字典樹（Trie）數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)基于字典樹的回文串檢測

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
    }
}

在這個實現(xiàn)中，我們首先創(chuàng)建了一個TrieNode類來表示字典樹的節(jié)點。然后，我們創(chuàng)建了一個PalindromeChecker類，其中包含一個字典樹的根節(jié)點以及插入和檢測回文串的方法。

insert方法用于將單詞插入字典樹。isPalindrome方法首先使用search方法找到給定單詞的最后一個字符對應的節(jié)點，然后調(diào)用isPalindromeHelper方法遞歸地檢查從兩端到中間的所有字符是否形成回文串。

isPalindromeHelper方法是一個遞歸方法，它檢查從給定節(jié)點開始的兩端字符是否形成回文串。如果遇到以元音結(jié)尾的單詞，它會跳過該元音字符。如果所有字符都形成回文串，則返回true，否則返回false。