Check If a Word Occurs As a Prefix of Any Word in a Sentence

class PrefixNode {
public:
    unordered_map<char, PrefixNode*> map;
    vector<int> positions;

    PrefixNode() {}
};

class PrefixTree {
public:
    PrefixNode* rootNode;

    PrefixTree() { rootNode = new PrefixNode(); }

    void insertWord(const string& word, int index) {
        PrefixNode* node = rootNode;
        for (char letter : word) {
            if (node->map.find(letter) == node->map.end()) {
                node->map[letter] = new PrefixNode();
            }
            node = node->map[letter];
            node->positions.push_back(index);
        }
    }

    vector<int> searchPrefix(const string& prefix) {
        PrefixNode* node = rootNode;
        for (char letter : prefix) {
            if (node->map.find(letter) == node->map.end()) {
                return {};
            }
            node = node->map[letter];
        }
        return node->positions;
    }
};

class Solution {
public:
    int isPrefixOfWord(string sentence, string searchWord) {
        PrefixTree prefixTree;
        istringstream wordsStream(sentence);
        string word;
        int wordIndex = 1;

        while (wordsStream >> word) {
            prefixTree.insertWord(word, wordIndex);
            wordIndex++;
        }

        vector<int> matchedPositions = prefixTree.searchPrefix(searchWord);

        return matchedPositions.empty() ? -1 : *min_element(matchedPositions.begin(), matchedPositions.end());
    }
};

To check if a word occurs as a prefix of any word in a sentence using C++, implement this solution that utilizes a custom Prefix Tree (Trie). Here's how you can structure your approach:

1. Define a PrefixNode class:

   • Create an unordered map to hold child nodes.
   • Use a vector to store positions where prefixes end.

2. Construct the PrefixTree class:

   • Start with a root PrefixNode.
   • insertWord function: For each word in the sentence, iterate over each character and if the character does not exist as a child of the current node, create a new node. Add the word's index to the positions vector of the last node of each word.
   • searchPrefix function: For the given prefix, traverse the tree. If a character from the prefix is not found, return an empty vector. If the traversal is successful, return the vector of word indices stored in the node of the last character of the prefix.

3. Define the Solution class and implement the isPrefixOfWord method:

   • Create an instance of PrefixTree.
   • Split the input sentence into words and insert each into the prefix tree with its index.
   • Search the prefix tree for the given prefix using the searchPrefix function.
   • If no matches are found, return -1. If matches exist, return the smallest index from the matched positions.

This approach efficiently determines if the search word is a prefix for any word in the sentence by leveraging the structured lookup capabilities of a Trie, thus minimizing unnecessary comparisons and optimizing performance, particularly for large datasets or frequent queries.

class TrieNode {

    Map<Character, TrieNode> childNodes;
    List<Integer> indexList;

    public TrieNode() {
        childNodes = new HashMap<>();
        indexList = new ArrayList<>();
    }
}

class Trie {

    TrieNode root;

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

    public void insertWord(String word, int idx) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            if (!node.childNodes.containsKey(ch)) {
                node.childNodes.put(ch, new TrieNode());
            }
            node = node.childNodes.get(ch);
            node.indexList.add(idx);
        }
    }

    public List<Integer> searchPrefix(String prefix) {
        TrieNode node = root;
        for (char ch : prefix.toCharArray()) {
            if (!node.childNodes.containsKey(ch)) {
                return new ArrayList<>();
            }
            node = node.childNodes.get(ch);
        }
        return node.indexList;
    }
}

class Solution {

    public int isPrefixOfWord(String sentence, String searchPrefix) {
        Trie trie = new Trie();
        String[] words = sentence.split(" ");
        for (int i = 1; i <= words.length; i++) {
            trie.insertWord(words[i - 1], i);
        }

        List<Integer> positions = trie.searchPrefix(searchPrefix);
        return positions.isEmpty() ? -1 : Collections.min(positions);
    }
}

The provided Java solution determines if a word occurs as a prefix of any word in a given sentence by utilizing a Trie data structure. Here's a breakdown of the solution:

• Define a TrieNode class, which includes a hash map for child nodes and a list to store indices of word appearances.

• Implement a Trie class with methods for inserting words and searching for words that start with a specific prefix.

• The insertWord method takes a word along with its index in the sentence, breaking the word into characters and storing the index at each character node.

• Utilize the searchPrefix method to move through the Trie based on characters of the prefix. If the prefix is found, the method returns the indices of the words starting with this prefix.

• The main functionality lies in the isPrefixOfWord method of the Solution class. This method:

  • Splits the sentence into words.
  • Inserts each word into the Trie with its respective 1-based index.
  • Searches for the minimum index of any word that begins with the given prefix using the Trie and returns it. If no such word exists, it returns -1.

This approach ensures efficient searching and storing of prefixes, making it an optimal solution for checking word occurrences as prefixes in sentences.

class TrieNode:
    def __init__(self):
        self.children = defaultdict(TrieNode)
        self.word_indices = []

class PrefixTrie:
    def __init__(self):
        self.root = TrieNode()

    def insert_word(self, word, index):
        node = self.root
        for character in word:
            node = node.children[character]
            node.word_indices.append(index)

    def find_prefix(self, prefix):
        node = self.root
        for character in prefix:
            if character not in node.children:
                return []
            node = node.children[character]
        return node.word_indices

class Solution:
    def isPrefixOfWord(self, sentence: str, searchWord: str) -> int:
        trie = PrefixTrie()
        words = sentence.split(" ")

        for index, word in enumerate(words, 1):
            trie.insert_word(word, index)

        indices = trie.find_prefix(searchWord)
        return min(indices) if indices else -1

The provided solution determines whether a word appears as a prefix of any word in a given sentence using a Trie data structure in Python. Here's a breakdown of the solution's execution:

• Initialization:

  • A TrieNode class is established with a defaultdict to dynamically create child nodes and a list, word_indices, to store indices of words where the prefix occurs.
  • A PrefixTrie class contains the root node of TrieNode and methods to insert words and find prefixes in the trie.

• Insertion of Words:

  • Words are inserted into the trie through the insert_word method. Each word from the sentence, along with its index (1-based), is added to the trie. While inserting, each character of the word is processed—moving deeper into the trie and updating node's word_indices with the current word's index.

• Prefix Search:

  • To determine if a given searchWord is a prefix, use the find_prefix method. Navigate through the trie by each character of the searchWord. If a character doesn't lead to any child node in the trie, it means the prefix is not present, and an empty list is returned.
  • If the traversal of searchWord completes successfully, return the list of indices where the prefix exists.

• Result Computation:

  • The isPrefixOfWord method of the Solution class initializes a PrefixTrie, splits the sentence into words, and uses the trie to find if searchWord occurs as a prefix in any of the words.
  • If the searchWord is found, it returns the minimum index from the list of indices indicating the earliest position that the prefix appears. Otherwise, it returns -1.

By utilizing a Trie for both insertion and search, this solution efficiently handles the query for prefixes over the list of words in a sentence.