Problem of The Day: Check If a Word Occurs As a Prefix of Any Word in a Sentence

Problem Statement

Intuition

The problem asks us to determine if a given searchWord is a prefix of any word in a sentence and return the index of the first occurrence. If it is not a prefix of any word, we return -1.

To solve this, we can use a Trie (prefix tree) to efficiently store and search prefixes within the words of the sentence. This approach is optimal for prefix-related queries due to the hierarchical structure of the Trie.

Approach

1. Split the Sentence: Break the sentence string into a list of words using the split() method.
2. Build a Trie:
   • For each word in the list, insert it into the Trie.
   • Keep track of the word index (1-based) as we add each character to the Trie.
3. Search for the Prefix:
   • Traverse the Trie with the characters of searchWord.
   • If a character in searchWord is not found in the Trie, return -1.
   • If we successfully traverse all characters in searchWord, return the stored index at the current Trie node.
4. If no prefix match is found after the traversal, return -1.

Complexity

• Time complexity:

  • Building the Trie: \(O(N \times L)\), where \(N\) is the number of words in the sentence and \(L\) is the average length of the words.
  • Searching in the Trie: \(O(M)\), where \(M\) is the length of searchWord.
  • Overall: \(O(N \times L + M)\).

• Space complexity:

  • Trie storage: \(O(N \times L)\), for storing all characters in the sentence.

Code

class Solution:
    def isPrefixOfWord(self, sentence: str, searchWord: str) -> int:
        trie = {}
        word_list = sentence.split()

        # Build the Trie
        for i, word in enumerate(word_list):
            curr = trie
            for c in word:
                if c not in curr:
                    curr[c] = {'idx': i + 1}
                curr = curr[c]
            curr['#'] = i + 1  # Mark the end of the word with its index

        # Search for the prefix in the Trie
        curr = trie
        for c in searchWord:
            if c not in curr:
                return -1  # Prefix not found
            curr = curr[c]

        return curr.get('idx', -1)  # Return the index of the first occurrence

Editorial

Approach 1: Brute Force

class Solution:
    def isPrefixOfWord(self, sentence: str, searchWord: str) -> int:
        # List to store the words from the sentence
        words_list = []
        # String to build the current word
        current_word = ""

        # Iterate through each character in the sentence
        for character in sentence:
            if character != " ":
                # Append the character to the current word
                current_word += character
            else:
                # If we encounter a space, add the current word to the list
                if current_word:
                    words_list.append(current_word)
                    current_word = ""  # Reset the string

        # Add the last word if the sentence doesn't end with a space
        if current_word:
            words_list.append(current_word)

        # Iterate through the list of words to find the prefix match
        for word_index, word in enumerate(words_list):
            if len(word) >= len(searchWord):
                is_match = True
                for char_index in range(len(searchWord)):
                    if word[char_index] != searchWord[char_index]:
                        is_match = False
                        break
                if is_match:
                    return word_index + 1  # Return 1-based index

        return -1  # Return -1 if no match is found

Approach 2: Two Pointer

class Solution:
    def isPrefixOfWord(self, sentence: str, searchWord: str) -> int:
        # Initialize the word position counter
        current_word_position = 1
        # Initialize the current index in the sentence
        current_index = 0
        # Get the length of the sentence
        sentence_length = len(sentence)

        # Loop through the sentence
        while current_index < sentence_length:
            # Skip leading spaces
            while (
                current_index < sentence_length
                and sentence[current_index] == " "
            ):
                current_index += 1
                current_word_position += 1

            # Check if the current word starts with searchWord
            matchCount = 0
            while (
                current_index < sentence_length
                and matchCount < len(searchWord)
                and sentence[current_index] == searchWord[matchCount]
            ):
                current_index += 1
                matchCount += 1

            # If the entire searchWord matches, return the current word position
            if matchCount == len(searchWord):
                return current_word_position

            # Move to the end of the current word
            while (
                current_index < sentence_length
                and sentence[current_index] != " "
            ):
                current_index += 1

        # If no match is found, return -1
        return -1

Approach 3: Using Built-In Function

class Solution:
    def isPrefixOfWord(self, sentence: str, searchWord: str) -> int:
        # Split the sentence into words
        words = sentence.split()
        # Iterate over the words with their positions (starting from 1)
        for i, word in enumerate(words, 1):
            # Check if the current word starts with the searchWord
            if word[: len(searchWord)] == searchWord:
                # If a match is found, return the current word position
                return i
        # If no match is found, return -1
        return -1