java如何编写前缀

前缀树的实现

在Java中实现前缀树（Trie）通常涉及创建一个节点类和一个树类。前缀树是一种树形结构，用于高效地存储和检索字符串集合中的键。

定义TrieNode类

每个节点包含子节点数组和一个标志表示是否为单词结尾。

class TrieNode {
    private TrieNode[] children;
    private boolean isEndOfWord;

    public TrieNode() {
        children = new TrieNode[26]; // 假设只处理小写字母
        isEndOfWord = false;
    }

    public boolean containsKey(char ch) {
        return children[ch - 'a'] != null;
    }

    public TrieNode get(char ch) {
        return children[ch - 'a'];
    }

    public void put(char ch, TrieNode node) {
        children[ch - 'a'] = node;
    }

    public void setEnd() {
        isEndOfWord = true;
    }

    public boolean isEnd() {
        return isEndOfWord;
    }
}

定义Trie类

Trie类包含插入、搜索和前缀搜索等基本操作。

class Trie {
    private TrieNode root;

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

    // 插入单词到前缀树
    public void insert(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            if (!node.containsKey(ch)) {
                node.put(ch, new TrieNode());
            }
            node = node.get(ch);
        }
        node.setEnd();
    }

    // 搜索完整单词
    public boolean search(String word) {
        TrieNode node = searchPrefix(word);
        return node != null && node.isEnd();
    }

    // 搜索前缀
    public boolean startsWith(String prefix) {
        TrieNode node = searchPrefix(prefix);
        return node != null;
    }

    private TrieNode searchPrefix(String prefix) {
        TrieNode node = root;
        for (char ch : prefix.toCharArray()) {
            if (!node.containsKey(ch)) {
                return null;
            }
            node = node.get(ch);
        }
        return node;
    }
}

使用示例

创建Trie实例并测试插入、搜索和前缀搜索功能。

public class Main {
    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        System.out.println(trie.search("apple"));   // 返回true
        System.out.println(trie.search("app"));     // 返回false
        System.out.println(trie.startsWith("app")); // 返回true
        trie.insert("app");
        System.out.println(trie.search("app"));     // 返回true
    }
}

处理更复杂字符

如果需要处理更广泛的字符集（如大写字母、数字等），可以调整TrieNode的实现。

class TrieNode {
    private Map<Character, TrieNode> children;
    private boolean isEndOfWord;

    public TrieNode() {
        children = new HashMap<>();
        isEndOfWord = false;
    }

    // 其他方法类似，使用Map替代数组
}

这种实现方式更灵活，适用于任意字符集，但可能占用更多内存。