1455. Check If a Word Occurs As a Prefix of Any Word in a Sentence
Problem Description
The challenge is to find out if a given searchWord
is a prefix of any word in the sentence
. The sentence
is a string made up of words separated by single spaces. A prefix is defined as the initial part of a word. If the searchWord
is found to be the prefix of one or more words in the sentence, we need to return the position of the first word (with the smallest index) where the searchWord
is a prefix. Otherwise, we return -1
. The words in the sentence are 1-indexed, meaning the first word is considered to be at position 1, the second word at position 2, and so on.
Intuition
The intuitive approach to solve this problem involves checking each word in the given sentence
to see if it starts with the searchWord
. We split the sentence
into individual words and iterate over them. With each iteration, we check whether the current word begins with the searchWord
using the startswith()
method. If we find a match, we return the current index, which corresponds to the position of the word in the sentence. If we finish iterating over all the words without finding a match, we return -1
as per the problem's requirement. The enumerate()
function coupled with a starting index of 1 is used to keep track of the word positions in a 1-indexed fashion.
Solution Approach
The solution uses a simple linear scan algorithm to solve the problem, which is efficient considering the problem's constraints. Since the sentence is guaranteed to have words separated by a single space, we can directly use the split()
function in Python, which, by default, splits the string by any whitespace, including spaces. This provides us with a list of words contained in the sentence.
With the list obtained, we proceed with the enumerate()
function, which iterates over the list and provides both the index and value of each item. However, to maintain the 1-indexed requirement, we start the enumeration from 1 by passing 1
as the second argument to enumerate()
.
During each iteration, we check for the prefix condition using the startswith()
method, which is a string method in Python that returns True
if the string starts with the specified prefix, False
otherwise.
The loop iterates through all words in the sentence. If a word is found that starts with searchWord
, the loop breaks, and the current index is returned. This index corresponds to the word's 1-indexed position in the original sentence. If no such word is found and the loop finishes, the function returns -1
to indicate the absence of a valid prefix match.
Here's the specific implementation from the provided code:
class Solution:
def isPrefixOfWord(self, sentence: str, searchWord: str) -> int:
# Split sentence into words and enumerate them starting from 1
for i, word in enumerate(sentence.split(), 1):
# Check if current word starts with searchWord
if word.startswith(searchWord):
return i # Return the 1-index position of the word
return -1 # Return -1 if no prefix match is found in any words
No additional data structures are used, and the startswith()
method provides a clean and readable way to check the prefix condition, making this solution straightforward and easy to understand.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's take the sentence
"hello world hi hey" and the searchWord
"he". We want to find out if "he" is a prefix of any word in the sentence
and return the position of the first word where "he" is a prefix.
The solution approach is as follows:
-
The
sentence
is split into individual words, giving us a list["hello", "world", "hi", "hey"]
. -
We use
enumerate()
to iterate over this list, starting indexing at 1 to match the problem's 1-indexed word position requirement. -
For each word, we check if the
searchWord
"he" is a prefix of the word using thestartswith()
method. -
We start with the first word "hello":
- "hello".startswith("he") is
True
. - Since this condition is true, and "hello" is the first word, we return its 1-index position, which is
1
.
- "hello".startswith("he") is
Therefore, in this example, the searchWord
"he" is a prefix of the word "hello", and the position returned is 1
.
If the searchWord
was "hi" instead, the steps would be followed until we reached the word "hi":
- "hello".startswith("hi") is
False
. - "world".startswith("hi") is
False
. - "hi".startswith("hi") is
True
, so we would return the 1-index position, which is3
in this case.
And if our searchWord
was something like "xyz", which isn't a prefix for any of the words:
- "hello".startswith("xyz") is
False
. - "world".startswith("xyz") is
False
. - "hi".startswith("xyz") is
False
. - "hey".startswith("xyz") is
False
.- Since no words start with "xyz", we reach the end of the iteration and return
-1
.
- Since no words start with "xyz", we reach the end of the iteration and return
Solution Implementation
1class Solution:
2 def isPrefixOfWord(self, sentence: str, search_word: str) -> int:
3 # Split the sentence into words
4 words = sentence.split()
5
6 # Enumerate over the words starting with an index of 1
7 for index, word in enumerate(words, start=1):
8 # Check if the current word starts with the search_word
9 if word.startswith(search_word):
10 # If search_word is a prefix, return the position of the word.
11 return index
12
13 # If no word starts with search_word, return -1
14 return -1
15
16# Example Usage:
17# sol = Solution()
18# result = sol.isPrefixOfWord("hello world", "wor")
19# print(result) # Outputs: 2 since "world" is the second word and has "wor" as a prefix
20
1class Solution {
2
3 // Method that finds if the searchWord is a prefix of any word in the sentence.
4 // If it is, returns the position (1-indexed) of the first occurrence. If not, returns -1.
5 public int isPrefixOfWord(String sentence, String searchWord) {
6 // Split the sentence into an array of individual words.
7 String[] words = sentence.split(" ");
8
9 // Iterate through each word in the array.
10 for (int i = 0; i < words.length; i++) {
11 // Check if the current word starts with the searchWord.
12 if (words[i].startsWith(searchWord)) {
13 // If it does, return the position of the word in the sentence, noting that index is 1-based.
14 return i + 1;
15 }
16 }
17 // If no word in the sentence is prefixed by searchWord, return -1.
18 return -1;
19 }
20}
21
1class Solution {
2public:
3 // Function to find if the searchWord is a prefix of any word in the sentence.
4 // Returns the word's index if found, otherwise returns -1.
5 int isPrefixOfWord(string sentence, string searchWord) {
6 // Initialize a stringstream with the given sentence
7 stringstream ss(sentence);
8
9 // Variable to store each word while extracting from the sentence
10 string currentWord;
11
12 // Variable to keep track of the word's index
13 int wordIndex = 1;
14
15 // Extract words one by one from the stringstream
16 while (ss >> currentWord) {
17 // Check if the current word starts with the searchWord
18 if (currentWord.find(searchWord) == 0) {
19 // If searchWord is a prefix of currentWord,
20 // return the current word's index
21 return wordIndex;
22 }
23 // Move to the next word
24 ++wordIndex;
25 }
26 // If the searchWord is not a prefix of any word, return -1
27 return -1;
28 }
29};
30
1/**
2 * Checks if the searchWord is a prefix of any word in a given sentence.
3 * If it is, returns the 1-based index of the first word where it's a prefix.
4 * Otherwise, returns -1.
5 *
6 * @param sentence - The sentence to search within.
7 * @param searchWord - The word to check as a prefix.
8 * @returns The 1-based index of the first word with the prefix or -1.
9 */
10function isPrefixOfWord(sentence: string, searchWord: string): number {
11 // Split the sentence into an array of words using space as a separator
12 const words = sentence.split(' ');
13
14 // Get the number of words in the array
15 const wordCount = words.length;
16
17 // Loop through the array of words
18 for (let index = 0; index < wordCount; index++) {
19 // Check if the current word starts with the searchWord
20 if (words[index].startsWith(searchWord)) {
21 // If it does, return the current index plus one (1-based index)
22 return index + 1;
23 }
24 }
25
26 // If no word starts with the searchWord, return -1
27 return -1;
28}
29
Time and Space Complexity
Time Complexity
The time complexity of the given code is O(n * k)
where n
is the number of words in the sentence and k
is the length of searchWord
. This is because:
- The
split()
method is called on the sentence, which takesO(m)
time, wherem
is the length of the sentence. - Every word is compared with
searchWord
usingstartswith()
, which in the worst case checks up tok
characters for each of then
words.
Space Complexity
The space complexity of the given code is O(n)
where n
is the number of words in the sentence. This is due to:
- The
split()
method, which creates a list of words from the sentence, storing each word as a separate element in the list. In the worst case, the list will containn
elements, thus takingO(n)
space.
Learn more about how to find time and space complexity quickly using problem constraints.
What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!