1455. 检查单词是否为句中其他单词的前缀

🟢   🔖  双指针 字符串 字符串匹配  🔗 力扣 LeetCode

题目

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 insentence _(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 <= 100
• 1 <= searchWord.length <= 10
• sentence consists of lowercase English letters and spaces.
• searchWord consists of lowercase English letters.

题目大意

给你一个字符串 sentence 作为句子并指定检索词为 searchWord ，其中句子由若干用 单个空格 分隔的单词组成。请你检查检索词 searchWord 是否为句子 sentence 中任意单词的前缀。

如果 searchWord 是某一个单词的前缀，则返回句子 sentence 中该单词所对应的下标（下标从 1 开始 ）。如果 searchWord 是多个单词的前缀，则返回匹配的第一个单词的下标（最小下标 ）。如果 searchWord 不是任何单词的前缀，则返回 -1**** 。

字符串 s 的 前缀 是 s 的任何前导连续子字符串。

示例 1：

输入： sentence = "i love eating burger", searchWord = "burg"

输出： 4

解释： "burg" 是 "burger" 的前缀，而 "burger" 是句子中第 4 个单词。

示例 2：

输入： sentence = "this problem is an easy problem", searchWord = "pro"

输出： 2

解释： "pro" 是 "problem" 的前缀，而 "problem" 是句子中第 2 个也是第 6 个单词，但是应该返回最小下标 2 。

示例 3：

输入： sentence = "i am tired", searchWord = "you"

输出： -1

解释： "you" 不是句子中任何单词的前缀。

提示：

• 1 <= sentence.length <= 100
• 1 <= searchWord.length <= 10
• sentence 由小写英文字母和空格组成。
• searchWord 由小写英文字母组成。

解题思路

1. 拆分句子为单词: 通过空格将 sentence 拆分成多个单词。

2. 遍历每个单词: 使用字符串的 startsWith 方法来检查 searchWord 是否为当前单词的前缀。

3. 返回第一个满足条件的索引:

   • 如果找到一个匹配的单词，直接返回其索引（从 1 开始）。
   • 如果遍历完成后没有找到，返回 -1。

复杂度分析

• 时间复杂度：O(n)。
  • 拆分句子为单词：O(n)，其中 n 是句子的总字符数。
  • 遍历每个单词并检查前缀：O(k * m)，其中 k 是单词的数量，m 是单词的平均长度。
  • 总时间复杂度：O(n)，因为 n 通常大于 k * m。
• 空间复杂度：O(k)，存储拆分后的单词数组需要 O(k) 的空间，k 是单词数量。

代码

/**
 * @param {string} sentence
 * @param {string} searchWord
 * @return {number}
 */
var isPrefixOfWord = function (sentence, searchWord) {
	// Step 1: 将句子拆分成单词
	const words = sentence.split(' ');

	// Step 2: 遍历单词数组
	for (let i = 0; i < words.length; i++) {
		// 检查 searchWord 是否是当前单词的前缀
		if (words[i].startsWith(searchWord)) {
			return i + 1; // Return the index (1-based)
		}
	}

	// Step 3: 如果没有匹配的单词前缀，返回 -1
	return -1;
};

相关题目

题号	标题	题解	标签	难度	力扣
2185	统计包含给定前缀的字符串	[✓]	数组 字符串 字符串匹配	🟢	🀄️ 🔗
2255	统计是给定字符串前缀的字符串数目	[✓]	数组 字符串	🟢	🀄️ 🔗