Bir sözün bir cümlənin hər hansı bir sözünün prefiksi kimi baş verdiyini yoxlayın

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Vəngilti
alqoritmlər kodlaşdırma müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutions SimBaxılıb 29

Problemin, bir cümlənin hər hansı bir sözün prefiksi kimi baş verdiyini yoxlayın leetcode həllində verilən axtarış sözü ilə başlayan sözün indeksini tapmağımızı xahiş etdi. Beləliklə, bizə bir cümlə olan bir cümlə verilir strings boşluqla ayrılmış və başqa bir sətir axtarış sözləridir. Bu axtarış sözünün cümlədəki hər hansı bir sözün prefiksi kimi olub olmadığını tapmaq üçün bizə deyilir. Söz bir prefiks şəklində meydana gəlir, bəzi sözlərin axtarış sözü ilə başlamalı olduğunu bildirir. Axtarış sözünün prefiksi olan birdən çox söz varsa, ən kiçik göstəricini qaytarın. Həmişəki kimi, həllin dərinliyinə dalmadan əvvəl bir neçə nümunəyə nəzər salaq. İndeksi qaytardıqda bizə 1 əsaslı indeksləşdirməni izləməyimiz tələb olunur.

Bir sözün bir cümlənin hər hansı bir sözünün prefiksi kimi baş verdiyini yoxlayınPin

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

İzahat: “burg” simli cümlədəki “burger” sözündə bir ön şəkilçi kimi mövcuddur. Axtarış sözünə bir ön söz kimi daxil olan tək bir söz olduğundan. Yalnız bu indeksi qaytarırıq.

Bir cümlənin hər hansı bir sözün prefiksi kimi bir sözün lekod həllində baş verdiyini yoxlamaq üçün yanaşma

Bir sözün bir cümlədəki hər hansı bir sözün bir prefiksi olaraq meydana gəldiyini yoxlayın problem Leetcode həllində bizə bir cümlə təqdim edir. Cümlə boş boşluqlarla ayrılmış bəzi sözlərdir. Bir cümlə boşluqla başlayıb bitmir. Bizə cümlədə axtarılması lazım olan bu cümlədən başqa bir simli və ya söz verilir. Daha sonra axtarış sözünün prefiksi olan bir sözün ən kiçik indeksini qaytarmağımız tələb olunur. Problemi həll etmək üçün ya ipi boşluqlara görə bölürük. Sonra yalnız sözlərin üstündən keçin və mövcud sözün axtarış sözü ilə başladığını yoxlayın. Bu əməliyyatı yerinə yetirmək Java-da split () və (with) açar sözləri ilə sadədir.

Problemi həll etmək üçün digər üsul, başlanğıcda cümləyə boşluq əlavə etməkdir. Bundan sonra, axtarış sözümüzün bir prefiksi olan hər hansı bir söz olub olmadığını tapmaq üçün find () funksiyasından istifadə edin və ya KMP alqoritmindən istifadə edin.

Bir sözün bir cümlənin hər hansı bir sözün bir prefiksi olaraq meydana gəldiyini yoxlamaq üçün kod bir leetcode həllində

C ++ kodu

#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 kodu

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N), çünki ən pis halda cümlənin hamısını dolaşırıq. Beləliklə, zamanın mürəkkəbliyi doğrudur.

Kosmik Mürəkkəblik

O (N), həllərin hər ikisində yeni bir sıra və ya yer tutan yeni bir simli yaradırıq.

Şərh yaz

Translate »
2