Үг өгүүлбэрийн Leetcode шийдэл дэх аливаа үгийн угтвар хэлбэрээр үүссэн эсэхийг шалгана уу


Хэцүү байдлын түвшин Easy
Байнга асуудаг Yelp
String

Өгүүлбэрийн Leetcode шийдэл дэх үгийн аль нэг үгийн угтвар болж байгаа эсэхийг шалгах асуудал нь өгөгдсөн хайлтын үгээр эхэлсэн үгийн индексийг олохыг биднээс хүссэн юм. Тиймээс, бидэнд зарим нэг өгүүлбэрийг өгч байна мөр зайгаар тусгаарлагдсан ба өөр мөр нь хайлтын үг юм. Энэхүү хайлтын үг нь өгүүлбэр доторх аль ч үгийн угтвар хэлбэрээр байгаа эсэхийг олохыг бидэнд хэллээ. Энэ үг угтвар хэлбэрээр гардаг бөгөөд зарим үг хайлтын үгнээс эхлэх ёстой гэсэн үг юм. Хэрэв хайлтын үгийг угтвар хэлбэрээр оруулсан нэгээс олон үг байгаа бол хамгийн жижиг индексийг буцаана уу. Уламжлалт ёсоор шийдэлд гүн орохоосоо өмнө хэдэн жишээг авч үзье. Бид индексийг буцааж өгөхдөө 1-д суурилсан индексжүүлэлтийг дагаж мөрдөх ёстой гэж хэлсэн.

Үг өгүүлбэрийн Leetcode шийдэл дэх аливаа үгийн угтвар хэлбэрээр үүссэн эсэхийг шалгана уу

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

Тайлбар: “burg” мөр нь өгүүлбэр дэх “бургер” гэсэн үгэнд угтвар хэлбэрээр байдаг. Хайлтын үгийг угтвар болгон оруулсан ганц л үг байдаг тул. Бид зөвхөн энэ индексийг буцааж өгдөг.

Үг өгүүлбэрийн Leetcode шийдэл дэх аливаа үгийн угтвар болж байгаа эсэхийг шалгах арга

Үг өгүүлбэрийн Leetcode шийдэл дэх аливаа үгийн угтвар болж байгаа эсэхийг шалгах нь бидэнд өгүүлбэр өгдөг. Өгүүлбэр нь хоосон зайгаар тусгаарлагдсан зарим үгс юм. Өгүүлбэр хоосон зайгаар эхэлж төгсгөл болохгүй. Мөн өгүүлбэрт хайх шаардлагатай энэ өгүүлбэрээс өөр тэмдэгт мөр эсвэл үгийг бидэнд өгсөн болно. Дараа нь хайлтын үгийг угтвар болгон оруулсан үгийн хамгийн жижиг индексийг буцааж өгөхийг бидэнд хэлэв. Асуудлыг шийдэхийн тулд мөрийг хоосон зайгаар хуваана. Дараа нь үгийг дайран өнгөрөөд, одоогийн үг хайх үгээр эхэлсэн эсэхийг шалгаарай. Энэ үйлдлийг гүйцэтгэх нь 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

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), шийдлүүдийн аль алинд нь бид шинэ массив эсвэл орон зайг эзэлдэг шинэ мөр үүсгэдэг.