შეამოწმეთ არის თუ არა სიტყვა, როგორც სიტყვათა წინაპირობა წინადადების Leetcode ამოხსნაში


Რთული ტური Easy
ხშირად ეკითხებიან Yelp
სიმებიანი

პრობლემა შეამოწმეთ, არსებობს თუ არა სიტყვა წინადადებას ნებისმიერი სიტყვის წინადადებაში Leetcode Solution გვთხოვდა ვიპოვნოთ სიტყვის ინდექსი, რომელიც მოცემული საძიებო სიტყვით იწყება. ასე რომ, მოცემულია წინადადება, რომელსაც აქვს რამდენიმე სიმები სივრცე და სხვა სტრიქონით გამოყოფილი საძიებო სიტყვაა. ჩვენ გვეუბნებიან, რომ გავარკვიოთ, არსებობს თუ არა ეს საძიებო სიტყვა, როგორც წინადადებაში ნებისმიერი სიტყვის პრეფიქსი. ეს სიტყვა გვხვდება, რადგან პრეფიქსი ნიშნავს, რომ ზოგიერთი სიტყვა უნდა დაიწყოს საძიებო სიტყვით. თუ არსებობს ერთზე მეტი სიტყვა, რომელსაც აქვს საძიებო სიტყვა, როგორც პრეფიქსი, დააბრუნეთ ყველაზე მცირე ინდექსი. როგორც ყოველთვის, ხსნარში სიღრმეში ჩასვლამდე მოდით ვნახოთ რამდენიმე მაგალითი. გვეუბნებიან, რომ ინდექსს დავუბრუნებთ, უნდა დავიცვათ 1 დაფუძნებული ინდექსაცია.

შეამოწმეთ არის თუ არა სიტყვა, როგორც სიტყვათა წინაპირობა წინადადების Leetcode ამოხსნაში

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

განმარტება: სტრიქონი "ბურგი" წინადადებაში არსებობს როგორც პრეფიქსი სიტყვაში "ბურგერი". მას შემდეგ, რაც არსებობს მხოლოდ ერთი სიტყვა, რომელსაც აქვს საძიებო სიტყვა, როგორც პრეფიქსი. ჩვენ მხოლოდ ამ მაჩვენებელს ვბრუნდებით.

მიდგომა შემოწმებისას, თუ სიტყვა წარმოიქმნება როგორც ნებისმიერი სიტყვის წინაპირობა წინადადებაში Leetcode Solution

პრობლემა შეამოწმეთ, არსებობს თუ არა სიტყვა წინადადებას ნებისმიერი სიტყვის წინადადებაში 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

ჯავის კოდი

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), ორივე გადაწყვეტილებაში ჩვენ ვქმნით ახალ მასივს ან ახალ სტრიქონს, რომელიც სივრცეს გვაკავშირებს.