Перевірте, чи слово зустрічається як префікс будь-якого слова в реченні з використанням Леткоду


Рівень складності Легко
Часто запитують у Дзявкати
рядок

Проблема Перевірити, якщо слово трапляється як префікс будь-якого слова у реченні Leetcode Solution, попросило нас знайти індекс слова, що починається з даного пошукового слова. Отже, нам дано речення, яке має дещо струни розділене пробілом, а інший рядок - це пошукове слово. Нам пропонують з’ясувати, чи існує це пошукове слово як префікс будь-якого слова у реченні. Слово зустрічається як префікс, що означає, що якесь слово має починатися з пошукового слова. Якщо існує більше одного слова, що має пошукове слово як префікс, поверніть найменший індекс. Отож, як зазвичай, перед тим, як зануритися глибоко в розчин, давайте поглянемо на кілька прикладів. Нам пропонують дотримуватися індексації на основі 1, коли ми повертаємо індекс.

Перевірте, чи слово зустрічається як префікс будь-якого слова в реченні з використанням Леткоду

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

Пояснення: Рядок “burg” існує як префікс у слові “burger” у реченні. Оскільки є лише одне слово, що має пошукове слово як префікс. Ми повертаємо лише цей індекс.

Підхід до перевірки, якщо слово зустрічається як префікс будь-якого слова у реченні з використанням Леткоду

Проблема Перевірити, чи слово зустрічається як префікс будь-якого слова у реченні Leetcode Solution, дає нам речення. У реченні є кілька слів, розділених пробілами. Речення не починається і не закінчується пробілом. Нам також пропонується рядок чи слово, крім цього речення, які потрібно шукати у реченні. Потім нам пропонують повернути найменший індекс слова, префіксом якого є слово пошуку. Отже, для вирішення проблеми ми розділяємо рядок відповідно до пробілів. Потім просто пройдітьсь по словах і перевірте, чи починається поточне слово з пошукового слова. Виконання цієї операції є простим у Java за допомогою ключових слів split () і startwith ().

Інший метод вирішення проблеми - це додати пробіл до речення на початку. Згодом використовуйте або функцію find (), або використовуйте алгоритм KMP, щоб знайти, чи існує якесь слово, що має наше пошукове слово як префікс.

Код для перевірки того, чи слово зустрічається як префікс будь-якого слова в реченні Leetcode Solution

Код С ++

#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

Аналіз складності

Складність часу

O (N), тому що в найгіршому випадку ми обходимо весь речення. Таким чином, складність часу є лінійною.

Складність простору

O (N), в обох рішеннях ми створюємо новий масив або новий рядок, який займає у нас простір.