Check If a Word Occurs As a Prefix of Any Word in a Sentence solution and explanation
Google
9 more videos on this problem
Check if a Word Occurs As a Prefix of Any Word in a Sentence | Leetcode 1455Technosage · 6:11 · 8K views
Check If a Word Occurs As a Prefix of Any Word in a Sentence | Leetcode 1455Techdose · 11:30 · 2K views
1455. Check If a Word Occurs As a Prefix of Any Word in a Sentence || LeetCode Easy C++, PythonCode with Alisha · 9:03 · 1K views
CHECK IF WORD OCCURS AS A PREFIX OF ANY WORD IN A SENTENCE | LEETCODE 1455 | PYTHON SOLUTIONCracking FAANG · 3:22 · 585 views
Leetcode | 1455. Check If a Word Occurs As a Prefix of Any Word in a Sentence | Easy | Java SolutionDeveloper Docs · 6:14 · 405 views
1455. Check If a Word Occurs As a Prefix of Any Word in a Sentence (Leetcode Easy)Programming Live with Larry · 3:33 · 372 views
LeetCode 1455 Check If a Word Occurs As a Prefix of Any Word in a Sentence | String | Easy | YelpCode Harmony · 10:42 · 349 views
Leetcode | 1455. Check If a Word Occurs As a Prefix of Any Word in a Sentence | Java | StringCakot Coding · 4:54 · 208 views
Check If a Word Occurs As a Prefix of Any Word in a Sentence (Leetcode 1455)Coding Interviews · 8:57 · 183 views
LeetCode : 1455. Check If a Word Occurs As a Prefix of Any Word in a Sentence Java ScriptOften Programmer · 6:59 · 160 views
The problem
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 <= 10sentenceconsists of lowercase English letters and spaces.searchWordconsists of lowercase English letters.
Approach overview
Problem Overview: Given a sentence containing words separated by spaces and a searchWord, return the 1-indexed position of the first word where searchWord appears as its prefix. If no word starts with that prefix, return -1.
Approach 1: Split and Compare using Simple Loop (Time: O(n * k), Space: O(n))
Split the sentence into individual words using the space delimiter, then iterate through the resulting array. For each word, check whether its first k characters match searchWord where k = searchWord.length. Most languages provide built-in helpers like startsWith or substring comparison, which keeps the implementation short and readable. This approach relies entirely on basic string operations and works well when clarity is more important than minimizing auxiliary memory.
Approach 2: Two-Pointer Traversal (Time: O(n), Space: O(1))
Instead of splitting the sentence, scan the string directly using two pointers. One pointer walks through the sentence character by character while another checks characters against searchWord when the start of a word is detected. A word boundary occurs at index 0 or immediately after a space. From each boundary, compare characters sequentially until either the prefix fully matches or a mismatch occurs. This avoids allocating an array of words and performs a single pass through the sentence. The technique is a practical use of two pointers combined with lightweight string matching.
Recommended for interviews: Both approaches are acceptable because the constraints are small and the logic is straightforward. Starting with the split-based loop demonstrates clear reasoning and correctness. The two-pointer traversal shows stronger control over string processing and space optimization, which interviewers often appreciate when discussing performance tradeoffs.
Approach 1: Split and Compare using Simple Loop
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.
def prefix_in_sentence(sentence, search_word):
words = sentence.split()
for index, word in enumerate(words):
if word.startswith(search_word):
return index + 1
return -1
# Example usage
sentence = "i love eating burger"
search_word = "burg"
print(prefix_in_sentence(sentence, search_word))public class PrefixFinder {
public static int prefixInSentence(String sentence, String searchWord) {
String[] words = sentence.split(" ");
for (int i = 0; i < words.length; i++) {
if (words[i].startsWith(searchWord)) {
return i + 1;
}
}
return -1;
}
public static void main(String[] args) {
String sentence = "i love eating burger";
String searchWord = "burg";
System.out.println(prefixInSentence(sentence, searchWord));
}
}#include <iostream>
#include <sstream>
#include <string>
using namespace std;
bool isPrefix(string word, string searchWord) {
return word.find(searchWord) == 0;
}
int prefixInSentence(string sentence, string searchWord) {
istringstream ss(sentence);
string word;
int index = 1;
while (ss >> word) {
if (isPrefix(word, searchWord))
return index;
index++;
}
return -1;
}
int main() {
string sentence = "i love eating burger";
string searchWord = "burg";
cout << prefixInSentence(sentence, searchWord) << endl;
return 0;
}function prefixInSentence(sentence, searchWord) {
const words = sentence.split(' ');
for (let i = 0; i < words.length; i++) {
if (words[i].startsWith(searchWord)) {
return i + 1;
}
}
return -1;
}
// Example usage
const sentence = "i love eating burger";
const searchWord = "burg";
console.log(prefixInSentence(sentence, searchWord));#include <stdio.h>
#include <string.h>
int isPrefix(char *word, char *searchWord) {
return strncmp(word, searchWord, strlen(searchWord)) == 0;
}
int prefixInSentence(char *sentence, char *searchWord) {
int index = 1;
char *word = strtok(sentence, " ");
while (word != NULL) {
if (isPrefix(word, searchWord))
return index;
word = strtok(NULL, " ");
index++;
}
return -1;
}
int main() {
char sentence[] = "i love eating burger";
char searchWord[] = "burg";
int result = prefixInSentence(sentence, searchWord);
printf("%d\n", result);
return 0;
}using System;
public class PrefixFinder {
public static int PrefixInSentence(string sentence, string searchWord) {
string[] words = sentence.Split(' ');
for (int i = 0; i < words.Length; i++) {
if (words[i].StartsWith(searchWord)) {
return i + 1;
}
}
return -1;
}
public static void Main() {
string sentence = "i love eating burger";
string searchWord = "burg";
Console.WriteLine(PrefixInSentence(sentence, searchWord));
}
}The split method breaks the sentence into a list of words. enumerate provides both a word and its index, and startswith is used for prefix checking. Returns 1-indexed position.
Time Complexity: O(n * m), where n is the number of words and m represents prefix checking.
Space Complexity: O(n) due to storing words in a list.
Approach 2: Two-Pointer Traversal
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.
def prefix_in_sentence(sentence, search_word):
index = 1
i = 0
while i < len(sentence):
if sentence[i] == ' ': # Skip spaces
i += 1
continue
j = 0
while i < len(sentence) and j < len(search_word) and sentence[i] == search_word[j]:
i += 1
j += 1
if j == len(search_word):
return index
while i < len(sentence) and sentence[i] != ' ': # Skip rest of the current word
i += 1
i += 1 # Skip the space after the word
index += 1
return -1
# Example usage
sentence = "i love eating burger"
search_word = "burg"
print(prefix_in_sentence(sentence, search_word))public class PrefixFinderTwoPointer {
public static int prefixInSentence(String sentence, String searchWord) {
int index = 1;
int i = 0;
while (i < sentence.length()) {
int j = 0;
int start = i;
while (i < sentence.length() && sentence.charAt(i) != ' ' && j < searchWord.length() && sentence.charAt(i) == searchWord.charAt(j)) {
i++;
j++;
}
if (j == searchWord.length()) return index;
while (i < sentence.length() && sentence.charAt(i) != ' ') i++;
index++;
i++; // Skip the space
}
return -1;
}
public static void main(String[] args) {
String sentence = "i love eating burger";
String searchWord = "burg";
System.out.println(prefixInSentence(sentence, searchWord));
}
}#include <iostream>
#include <string>
using namespace std;
int prefixInSentence(string sentence, string searchWord) {
int index = 1; // word index
int i = 0;
while (i < sentence.length()) {
if (sentence[i] == ' ') {
i++;
continue;
}
int j = 0;
int start = i;
while (i < sentence.length() && sentence[i] != ' ' && j < searchWord.length() && sentence[i] == searchWord[j]) {
i++;
j++;
}
if (j == searchWord.length()) return index;
while (i < sentence.length() && sentence[i] != ' ') i++;
index++;
}
return -1;
}
int main() {
string sentence = "i love eating burger";
string searchWord = "burg";
cout << prefixInSentence(sentence, searchWord) << endl;
return 0;
}function prefixInSentence(sentence, searchWord) {
let index = 1;
let i = 0;
while (i < sentence.length) {
if (sentence[i] === ' ') {
i++;
continue;
}
let j = 0;
while (i < sentence.length && sentence[i] !== ' ' && j < searchWord.length && sentence[i] === searchWord[j]) {
i++;
j++;
}
if (j === searchWord.length) {
return index;
}
while (i < sentence.length && sentence[i] !== ' ') {
i++;
}
i++; // Move to the next word
index++;
}
return -1;
}
// Example usage
console.log(prefixInSentence("i love eating burger", "burg"));#include <stdio.h>
#include <string.h>
int prefixInSentence(char *sentence, char *searchWord) {
int index = 1, i = 0, j = 0;
while (sentence[i]) {
if (sentence[i] == ' ' || i == 0) {
if (i != 0) i++;
j = 0;
while (sentence[i] && sentence[i] != ' ' && searchWord[j] && sentence[i] == searchWord[j]) {
i++;
j++;
}
if (!searchWord[j]) return index;
while (sentence[i] && sentence[i] != ' ') i++;
index++;
} else i++;
}
return -1;
}
int main() {
char sentence[] = "i love eating burger";
char searchWord[] = "burg";
int result = prefixInSentence(sentence, searchWord);
printf("%d\n", result);
return 0;
}using System;
public class PrefixFinderTwoPointer {
public static int PrefixInSentence(string sentence, string searchWord) {
int index = 1;
int i = 0;
while (i < sentence.Length) {
if (sentence[i] == ' ') {
i++;
continue;
}
int j = 0;
int start = i;
while (i < sentence.Length && sentence[i] != ' ' && j < searchWord.Length && sentence[i] == searchWord[j]) {
i++;
j++;
}
if (j == searchWord.Length) return index;
while (i < sentence.Length && sentence[i] != ' ') i++;
index++;
i++; // Move to next word
}
return -1;
}
public static void Main() {
Console.WriteLine(PrefixInSentence("i love eating burger", "burg"));
}
}A straightforward two-pointer style implementation where i traverses the sentence and j tries to match the search_word. The pointer skips spaces smartly, and converges on a solution quickly.
Time Complexity: O(n) since you're efficiently iterating over the sentence.
Space Complexity: O(1).
Approach 3: String Splitting
We split sentence by spaces into words, then iterate through words to check if words[i] is a prefix of searchWord. If it is, we return i+1. If the iteration completes and no words satisfy the condition, we return -1.
The time complexity is O(m times n), and the space complexity is O(m). Here, m and n are the lengths of sentence and searchWord, respectively.
function isPrefixOfWord(sentence: string, searchWord: string): number {
const ss = sentence.split(/\s/);
const n = ss.length;
for (let i = 0; i < n; i++) {
if (ss[i].startsWith(searchWord)) {
return i + 1;
}
}
return -1;
}func isPrefixOfWord(sentence string, searchWord string) int {
for i, s := range strings.Split(sentence, " ") {
if strings.HasPrefix(s, searchWord) {
return i + 1
}
}
return -1
}impl Solution {
pub fn is_prefix_of_word(sentence: String, search_word: String) -> i32 {
let ss = sentence.split_whitespace().collect::<Vec<&str>>();
for i in 0..ss.len() {
if ss[i].starts_with(&search_word) {
return (i + 1) as i32;
}
}
-1
}
}class Solution {
/**
* @param String $sentence
* @param String $searchWord
* @return Integer
*/
function isPrefixOfWord($sentence, $searchWord) {
$words = explode(' ', $sentence);
for ($i = 0; $i < count($words); ++$i) {
if (strpos($words[$i], $searchWord) === 0) {
return $i + 1;
}
}
return -1;
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Split and Compare using Simple Loop | Time Complexity: |
| Two-Pointer Traversal | Time Complexity: |
| String Splitting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Split and Compare using Simple Loop | O(n * k) | O(n) | When readability matters and using built-in string helpers like startsWith is acceptable. |
| Two-Pointer Traversal | O(n) | O(1) | When you want a single-pass scan without allocating extra memory for split words. |
Frequently asked questions
Is Check If a Word Occurs As a Prefix of Any Word in a Sentence easy or hard?
LeetCode classifies this problem as Easy with an acceptance rate around 68%. The logic involves basic string iteration and prefix comparison, making it suitable for beginners practicing string manipulation and simple two-pointer techniques.
Check If a Word Occurs As a Prefix of Any Word in a Sentence Python/Java solution
In Python or Java, iterate through each word and check if it starts with searchWord using built-in methods like startswith or startsWith. Return the 1-indexed position of the first matching word, otherwise return -1. A more optimized implementation scans the sentence directly using two pointers for O(1) space.
How to solve Check If a Word Occurs As a Prefix of Any Word in a Sentence in O(n)?
Traverse the sentence once while tracking word boundaries. When you encounter the start of a word (index 0 or after a space), compare characters sequentially with searchWord. If all characters match, return the word index. Because each character in the sentence is processed at most once, the total runtime remains O(n).
What is the best approach for Check If a Word Occurs As a Prefix of Any Word in a Sentence?
The most practical approach is scanning the sentence and checking each word's prefix. A two-pointer traversal achieves this in O(n) time and O(1) space by detecting word boundaries and matching characters with searchWord. A simpler alternative is splitting the sentence into words and using a startsWith comparison.
Is Check If a Word Occurs As a Prefix of Any Word in a Sentence asked at Google/Amazon/Meta?
Prefix and string scanning problems appear frequently in interviews at companies like Amazon, Google, and Meta, especially in easy or warm-up rounds. This problem tests understanding of string traversal, prefix matching, and careful handling of word boundaries.
What data structure is used in Check If a Word Occurs As a Prefix of Any Word in a Sentence?
The problem primarily uses basic string processing. The split-based solution temporarily stores words in an array, while the optimal approach uses two pointers directly on the input string without additional data structures.
What is the time complexity of Check If a Word Occurs As a Prefix of Any Word in a Sentence?
The typical solution runs in O(n) to O(n * k) time where n is the sentence length and k is the length of searchWord. Each word is checked only until the prefix either matches or fails. Space complexity is O(1) with a pointer scan or O(n) if the sentence is split into an array of words.