Проверете дали некој збор се јавува како префикс на кој било збор во решение за леткод на реченица  


Ниво на тешкотија Лесно
Често прашувано во Yelp
алгоритми кодирање интервју интервју подготви LeetCode LeetCodeSolutions Стринг

Проблемот Проверете дали некој збор се јавува како префикс на кој било збор во реченица Решение за лек-код побара од нас да го најдеме индексот на зборот што започнува со даден збор за пребарување. Значи, ни е дадена реченица која има некои жици одделени со празно место и друга низа е збор за пребарување. Ни е кажано да откриеме дали овој збор за пребарување постои како префикс на кој било збор во реченицата. Зборот се јавува како префикс значи дека некој збор треба да започне со зборот за пребарување. Ако има повеќе од еден збор што го има префиксот на зборот за пребарување, вратете го најмалиот индекс. Така, како и обично, пред да се нурнеме длабоко во решението, да разгледаме неколку примери. Ни е кажано да следиме индексирање засновано на 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

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

Временска комплексност

НА), затоа што ја минуваме целата реченица во најлош случај. Така, временската сложеност е линеарна.

Комплексноста на просторот

НА), во двата решенија создаваме нова низа или нова низа што ни одзема простор.