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 PalindromePrefixSearch {
    private TrieNode root;

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

    // 插入字符串到Trie树中
    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 hasPalindromePrefix(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) {
        PalindromePrefixSearch search = new PalindromePrefixSearch();
        search.insert("level");
        search.insert("apple");
        search.insert("madam");
        search.insert("banana");

        System.out.println(search.hasPalindromePrefix("mad")); // 输出: true
        System.out.println(search.hasPalindromePrefix("app")); // 输出: false
        System.out.println(search.hasPalindromePrefix("ban")); // 输出: true
    }
}

在这个实现中，我们首先定义了一个TrieNode类，用于表示Trie树的节点。每个节点包含一个字符到TrieNode的映射（children），以及一个布尔值（isEndOfWord），表示该节点是否是一个单词的结尾。

接下来，我们创建了一个PalindromePrefixSearch类，用于实现基于Trie树的回文串前缀搜索。我们定义了一个insert方法，用于将字符串插入到Trie树中。我们还定义了一个hasPalindromePrefix方法，用于检查是否存在给定前缀的回文串。

在main方法中，我们创建了一个PalindromePrefixSearch实例，并插入了一些字符串。然后，我们使用hasPalindromePrefix方法检查是否存在给定前缀的回文串，并将结果打印到控制台。