Given a sentence that consists of some words separated by a single space, and a searchWord, check if searchWord is a prefix of any word in sentence.
Return the index of the word in sentence (1-indexed) where searchWord is a prefix of this word. If searchWord is a prefix of more than one word, return the index of the first word (minimum index). If there is no such word return -1.
A prefix of a string s is any leading contiguous substring of s.
Example 1:
Input: sentence = "i love eating burger", searchWord = "burg" Output: 4 Explanation: "burg" is prefix of "burger" which is the 4th word in the sentence.
Example 2:
Input: sentence = "this problem is an easy problem", searchWord = "pro" Output: 2 Explanation: "pro" is prefix of "problem" which is the 2nd and the 6th word in the sentence, but we return 2 as it's the minimal index.
Example 3:
Input: sentence = "i am tired", searchWord = "you" Output: -1 Explanation: "you" is not a prefix of any word in the sentence.
Constraints:
1 <= sentence.length <= 1001 <= searchWord.length <= 10sentence consists of lowercase English letters and spaces.searchWord consists of lowercase English letters.This method involves splitting the input sentence into words and then iterating through each word to check if the searchWord is a prefix of that word. If a match is found, the index of the word (1-based) is returned. If no match is found, -1 is returned.
Using strtok to split the sentence into words. For each word, strncmp checks if the searchWord is a prefix. The index is returned if found; otherwise, it continues. If no prefix is found, -1 is returned.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n * m) where n is the number of words and m is the average length of words.
Space Complexity: O(1).
This approach uses a two-pointer technique to traverse the sentence and words simultaneously for efficient prefix checking. It doesn't rely on splitting the string into words but rather navigates the sentence using custom logic.
Utilizes two pointers: i for traversing the sentence and j for the searchWord. Iterates character by character to check prefix while tracking spaces to identify words and reset checks.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) where n is the length of the sentence, as it efficiently traverses the string.
Space Complexity: O(1) as only pointers are used.
| Approach | Complexity |
|---|---|
| Split and Compare using Simple Loop | Time Complexity: |
| Two-Pointer Traversal | Time Complexity: |
Check if a Word Occurs As a Prefix of Any Word in a Sentence | Leetcode 1455 • Technosage • 4,887 views views
Watch 9 more video solutions →Practice Check If a Word Occurs As a Prefix of Any Word in a Sentence with our built-in code editor and test cases.
Practice on FleetCode