Праверце, ці сустракаецца слова як прэфікс любога слова ў вырашэнні з леткадрам сказа


Узровень складанасці Лёгка
Часта пытаюцца ў Скуголіць
Радок

Праблема Праверка, калі слова сустракаецца як прэфікс любога слова ў сказе Leetcode Solution папрасіла нас знайсці індэкс слова, які пачынаецца з дадзенага слова пошуку. Такім чынам, нам дадзены прысуд, які мае некаторыя радкі падзелена прабелам і іншы радок - гэта пошукавае слова. Нам кажуць, каб даведацца, ці існуе гэтае слова для пошуку як прэфікс любога слова ў сказе. Слова, якое сустракаецца як прэфікс, азначае, што якое-небудзь слова павінна пачынацца з пошукавага слова. Калі існуе больш за адно слова, у якім слова пошуку знаходзіцца ў якасці прэфікса, вярніце найменшы індэкс. Такім чынам, як звычайна, перад тым, як паглыбіцца ў раствор, разбярэм некалькі прыкладаў. Нам кажуць прытрымлівацца індэксацыі на аснове 1, калі мы вяртаем індэкс.

Праверце, ці сустракаецца слова як прэфікс любога слова ў вырашэнні з леткадрам сказа

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

Тлумачэнне: радок "бург" існуе як прыстаўка да слова "бургер" у сказе. Паколькі ёсць толькі адно слова, якое мае ў якасці прэфікса слова для пошуку. Мы вяртаем толькі гэты індэкс.

Падыход для праверкі, калі слова сустракаецца як прэфікс любога слова ў вырашэнні з леткадрам сказа

Праблема "Праверка", калі слова сустракаецца як прэфікс любога слова ў сказе "Леткод". Дае нам сказ. Сказ - гэта некаторыя словы, падзеленыя прабеламі. Прапанова не пачынаецца і не заканчваецца прабелам. Нам таксама прадастаўляецца радок ці слова, акрамя гэтага сказа, якія трэба шукаць у сказе. Затым нам прапануюць вярнуць найменшы індэкс слова, прэфіксам якога з'яўляецца слова для пошуку. Такім чынам, для вырашэння праблемы мы падзяляем радок у адпаведнасці з прабеламі. Тады проста перабярыце словы і праверце, ці пачынаецца бягучае слова з пошукавага слова. Выкананне гэтай аперацыі проста ў Java з ключавымі словамі split () і startwith ().

Іншы метад вырашэння праблемы - дадаць прабел у сказ у самым пачатку. Пасля выкарыстоўвайце альбо функцыю find (), альбо выкарыстоўвайце алгарытм KMP, каб знайсці, ці існуе якое-небудзь слова, прэфіксам якога з'яўляецца наша пошукавае слова.

Код, каб праверыць, ці сустракаецца слова як прэфікс любога слова ў вырашэнні з леткадрам сказа

Код 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

Аналіз складанасці

Складанасць часу

O (N), таму што мы пераходзім увесь сказ у горшым выпадку. Такім чынам, складанасць часу лінейная.

Касмічная складанасць

O (N), у абодвух рашэннях мы ствараем новы масіў альбо новы радок, які займае ў нас месца.