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），以及插入、搜索和前綴檢查的方法。插入方法將一個字符串的每個字符按順序插入到回文前綴樹中；搜索方法檢查回文前綴樹中是否存在某個字符串；前綴檢查方法檢查回文前綴樹中是否存在某個字符串的前綴。