Untitled

 avatar
unknown
plain_text
14 days ago
2.9 kB
2
Indexable
class Trie {
    Trie[] links;
    boolean flag; // Marks the end of a word
    int childCount; // Number of children for the current node

    public Trie() {
        links = new Trie[26];
        flag = false;
        childCount = 0; // Initialize child count to 0
    }

    // Check if the current node has a link for the given character
    boolean containsKey(char ch) {
        return links[ch - 'a'] != null;
    }

    // Add a new Trie node for the given character
    void put(char ch, Trie newTrie) {
        links[ch - 'a'] = newTrie;
    }

    // Get the Trie node for the given character
    Trie get(char ch) {
        return links[ch - 'a'];
    }

    // Set the current node as the end of a word
    void setWordEndFlag() {
        flag = true;
    }

    // Check if the current node marks the end of a word
    boolean getWordEndFlag() {
        return flag;
    }
}

public class TrieOperations {
    private Trie root;

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

    // Insert a word into the Trie
    public void insert(String word) {
        Trie temp = root;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            if (!temp.containsKey(ch)) {
                temp.put(ch, new Trie());
                temp.childCount++; // Increment child count for the current node
            }
            temp = temp.get(ch);
        }
        temp.setWordEndFlag();
    }

    // Find the length of the Longest Common Prefix (LCP)
    public int findLongestCommonPrefixLength(String referenceWord) {
        Trie temp = root;
        int length = 0;

        for (int i = 0; i < referenceWord.length(); i++) {
            char ch = referenceWord.charAt(i);

            // If the current node has only one child and is not a word-ending node
            if (temp.childCount == 1 && !temp.getWordEndFlag() && temp.containsKey(ch)) {
                length++; // Increment the LCP length
                temp = temp.get(ch);
            } else {
                break; // Stop if branching occurs or we reach the end of a common prefix
            }
        }

        return length;
    }

    public static void main(String[] args) {
        TrieOperations trie = new TrieOperations();

        // Insert words into the Trie
        System.out.println("Inserting words: Striver, Striving, String, Strike");
        trie.insert("striver");
        trie.insert("striving");
        trie.insert("string");
        trie.insert("strike");

        // Use the first inserted word to find the LCP length
        String referenceWord = "striver"; // Use any word that has been inserted
        System.out.println("Length of Longest Common Prefix: " + trie.findLongestCommonPrefixLength(referenceWord));
    }
}
Editor is loading...
Leave a Comment