Java實現(xiàn)基于Trie樹的回文串前綴搜索

Trie樹（前綴樹）是一種用于存儲字符串的樹形結(jié)構(gòu)，它可以高效地進行字符串的前綴搜索

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

在這個實現(xiàn)中，我們首先定義了一個TrieNode類，用于表示Trie樹的節(jié)點。每個節(jié)點包含一個字符到TrieNode的映射（children），以及一個布爾值（isEndOfWord），表示該節(jié)點是否是一個單詞的結(jié)尾。

接下來，我們創(chuàng)建了一個PalindromePrefixSearch類，用于實現(xiàn)基于Trie樹的回文串前綴搜索。我們定義了一個insert方法，用于將字符串插入到Trie樹中。我們還定義了一個hasPalindromePrefix方法，用于檢查是否存在給定前綴的回文串。

在main方法中，我們創(chuàng)建了一個PalindromePrefixSearch實例，并插入了一些字符串。然后，我們使用hasPalindromePrefix方法檢查是否存在給定前綴的回文串，并將結(jié)果打印到控制臺。