检查单词在句子Leetcode解决方案中是否作为任何单词的前缀出现


难度级别 易得奖学金
经常问 狗吠声

问题:检查单词是否作为句子中任何单词的前缀出现Leetcode解决方案要求我们找到以给定搜索词开头的单词的索引。 因此,我们得到一个句子,其中包含一些 字符串 用空格分隔,另一个字符串是搜索词。 我们被告知要查找该搜索词是否作为句子中任何词的前缀存在。 该词作为前缀出现,意味着某些词应以搜索词开头。 如果存在多个以搜索词为前缀的词,则返回最小的索引。 因此,像往常一样,在深入研究解决方案之前,让我们看一些示例。 返回索引时,我们被告知遵循基于1的索引。

检查单词在句子Leetcode解决方案中是否作为任何单词的前缀出现

sentence = "i love eating burger", searchWord = "burg"
4

说明:字符串“ burg”作为句子中“ burger”一词的前缀存在。 由于只有一个单词具有搜索词作为前缀。 我们仅返回该索引。

在句子Leetcode解决方案中检查单词是否作为任何单词的前缀出现的方法

在句子Leetcode解决方案中,检查单词是否作为任何单词的前缀出现的问题为我们提供了一个句子。 句子是用空格隔开的一些单词。 句子不能以空格开头和结尾。 除此句子外,我们还提供了需要在句子中搜索的字符串或单词。 然后,我们被告知返回以搜索词为前缀的单词的最小索引。 因此,要解决该问题,我们要么按照空格分割字符串。 然后只需遍历单词并检查当前单词是否以搜索单词开头。 在Java中,使用split()和startswith()关键字执行此操作很简单。

解决该问题的另一种方法是在句子开头添加一个空格。 之后,使用find()函数或使用KMP算法查找是否存在以我们的搜索词为前缀的词。

用于检查单词在句子Leetcode解决方案中是否作为任何单词的前缀出现的代码

C ++代码

#include <bits/stdc++.h>
using namespace std;

int isPrefixOfWord(string sentence, string searchWord) {
    string newSentence = " " + sentence, word = " " + searchWord;
    auto pos = newSentence.find(word);
    if (pos != string::npos)
        return count(begin(newSentence), begin(newSentence) + pos + 1, ' ');
    return -1;
}

int main(){
    string sentence = "i love eating burger";
    string searchWord = "burg";
    cout<<isPrefixOfWord(sentence, searchWord);
}
4

Java代码

import java.util.*;
import java.lang.*;
import java.io.*;

class Rough {
    public static int isPrefixOfWord(String sentence, String searchWord) {
        String[] words = sentence.split(" ");
        for (int i = 1; i <= words.length; ++i) {
            if (words[i - 1].startsWith(searchWord)) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) throws IOException {
        String sentence = "i love eating burger";
        String searchWord = "burg";

        System.out.print(isPrefixOfWord(sentence, searchWord));
    }
}
4

复杂度分析

时间复杂度

上), 因为在最坏的情况下,我们会遍历整个句子。 因此,时间复杂度是线性的。

空间复杂度

上), 在这两种解决方案中,我们都会创建一个占用我们空间的新数组或新字符串。