تحقق من حدوث كلمة كبادئة لأي كلمة في حل Leetcode الجملة


مستوى الصعوبة سهل
كثيرا ما يطلب في عواء
خيط

المشكلة "تحقق مما إذا كانت كلمة حدثت كبادئة لأي كلمة في جملة جملة" طلب حل Leetcode العثور على فهرس الكلمة الذي يبدأ بكلمة بحث معينة. لذلك ، حصلنا على جملة تحتوي على بعض سلاسل مفصولة بمسافة وسلسلة أخرى هي كلمة بحث. يُطلب منا معرفة ما إذا كانت كلمة البحث هذه موجودة كبادئة لأي كلمة في الجملة. تحدث الكلمة كبادئة تعني أن بعض الكلمات يجب أن تبدأ بكلمة البحث. إذا كان هناك أكثر من كلمة واحدة تحتوي على كلمة البحث كبادئة ، فقم بإرجاع أصغر فهرس. كالمعتاد ، قبل التعمق في الحل ، دعونا نلقي نظرة على بعض الأمثلة. يُطلب منا اتباع الفهرسة المستندة إلى 1 عندما نعيد الفهرس.

تحقق من حدوث كلمة كبادئة لأي كلمة في حل Leetcode الجملة

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

Explanation: السلسلة "burg" موجودة كبادئة في كلمة "burger" في الجملة. نظرًا لوجود كلمة واحدة فقط لها كلمة البحث كبادئة. نعيد هذا الفهرس فقط.

نهج للتحقق مما إذا كانت الكلمة تحدث كبادئة لأي كلمة في حل Leetcode الجملة

المشكلة تحقق مما إذا كانت كلمة ما تحدث كبادئة لأي كلمة في جملة حل Leetcode يزودنا بجملة. الجملة عبارة عن بعض الكلمات مفصولة بمسافات فارغة. الجملة لا تبدأ وتنتهي بمسافة فارغة. تم تزويدنا أيضًا بسلسلة أو كلمة غير هذه الجملة التي يجب البحث عنها في الجملة. يُطلب منا بعد ذلك إرجاع أصغر فهرس للكلمة التي تحتوي على كلمة البحث كبادئة لها. لذا لحل المشكلة إما أن نقوم بتقسيم الخيط وفقًا للمسافات. ثم قم بالمرور فوق الكلمات وتحقق مما إذا كانت الكلمة الحالية تبدأ بكلمة البحث. إجراء هذه العملية بسيط في Java باستخدام كلمات مفتاحية Split () و startswith ().

الطريقة الأخرى لحل المشكلة هي إضافة مسافة إلى الجملة في البداية. بعد ذلك ، استخدم إما وظيفة البحث () أو استخدم خوارزمية 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) في كلا الحلين نقوم بإنشاء مصفوفة جديدة أو سلسلة جديدة تأخذنا إلى الفضاء.