Проверете дали дадена дума се появява като префикс на която и да е дума в решението на Leetcode на изречението


Ниво на трудност Лесно
Често задавани в Лая
Низ

Проблемът Проверете дали дадена дума се среща като префикс на която и да е дума в изречение Leetcode Solution ни помоли да намерим индекса на думата, която започва с дадена дума за търсене. И така, получаваме изречение, което има някои струни разделен с интервал и друг низ е дума за търсене. Казват ни да открием дали тази дума за търсене съществува като префикс на която и да е дума в изречението. Думата се появява като префикс означава, че някои думи трябва да започват с думата за търсене. Ако съществува повече от една дума, която има думата за търсене като префикс, върнете най-малкия индекс. Така че, както обикновено, преди да се потопите дълбоко в решението, нека разгледаме няколко примера. Казва ни се да следваме индексиране на базата на 1, когато върнем индекса.

Проверете дали дадена дума се появява като префикс на която и да е дума в решението на Leetcode на изречението

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

Обяснение: Низът „burg“ съществува като префикс в думата „burger“ в изречението. Тъй като има само една дума, която има думата за търсене като префикс. Връщаме само този индекс.

Подход за проверка, ако дадена дума се появи като префикс на която и да е дума в решението на Leetcode на изречението

Проблемът Проверете дали дадена дума се появява като префикс на която и да е дума в изречение Leetcode Solution ни предоставя изречение. Изречението е няколко думи, разделени с празни интервали. Изречението не започва и не завършва с празно пространство. Освен това ни се предоставя низ или дума, различни от това изречение, които трябва да се търсят в изречението. След това ни се казва да върнем най-малкия индекс на дума, чиято префикс е думата за търсене. За да решим проблема, или разделяме низа според интервалите. След това просто преминете през думите и проверете дали текущата дума започва с думата за търсене. Изпълнението на тази операция е лесно в Java с ключови думи split () и startwith ().

Другият метод за решаване на проблема е добавяне на интервал към изречението в началото. След това използвайте функцията 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

Анализ на сложността

Сложност във времето

НА), защото в най-лошия случай прекосяваме цялото изречение. По този начин сложността на времето е линейна.

Сложност на пространството

НА), и в двете решения създаваме нов масив или нов низ, който ни отнема място.