وګورئ چې که یوه جمله د لیوټ کوډ په محلول کې د کوم ټکي سره د لومړي مخ په توګه پیښ شي


مشکل کچه په اسانۍ سره
په مکرر ډول دننه پوښتل کیږي Yelp
تار

ستونزه وڅیړئ که چیرې یو ټکی په یوه جمله کې د کوم ټکي مخکښ په توګه پیښ شي لیټکوډ حل د موږ څخه غوښتنه وکړه چې د کلمې شاخص ومومئ چې د ورکړل شوي لټون ټکي سره پیل کیږي. نو ، موږ ته یوه جمله راکول کیده چې یو څه لري ځړونه د ځای په واسطه جلا شوی او بل تار د لټون کلمه ده. موږ ته ویل شوي چې ومومي که دا د لټون ټکي په جمله کې د هرې کلمې د مختاړی په توګه شتون ولري. کلمه د مختاړی په توګه پیښیږي پدې معنی چې یو څه ټکی باید د لټون کلمې سره پیل شي. که چیرې د یوې څخه ډیر ټکي شتون ولري چې د مخ کلمې په توګه د لټون کلمه لري ، نو کوچنی شاخص بیرته راستانه کړئ. نو د معمول په څیر ، مخکې له دې چې حل ته ژور غوږ شئ راځئ چې یو څو مثالونو ته یوه کتنه وکړو. موږ ته ویل کیږي چې د 1 پر اساس شاخص تعقیب کړئ کله چې موږ شاخص بیرته راولو.

وګورئ چې که یوه جمله د لیوټ کوډ په محلول کې د کوم ټکي سره د لومړي مخ په توګه پیښ شي

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

توضیحي: د "برګ" تار په جمله کې د "برګر" په ټکي کې د ماډل په توګه شتون لري. ځکه چې دلته یوازې یو ټکی شتون لري چې د مختاړی په توګه د لټون کلمه لري. موږ یوازې دا شاخص بیرته راوړو.

د چک لپاره لارښود که چیرې یو ټکی په جمله د لیټکوډ حل کې د هر ټکي د مختاړي په توګه پیښ شي

ستونزه وڅیړئ که چیرې یو ټکی په یوه جمله کې د کوم ټکي سره د مخکښ په توګه پیښ شي لیټکوډ حل موږ ته یوه جمله چمتو کوي. جمله یو څو ټکي دي چې تش ځایونه سره جلا کیږي. یوه جمله په تشه ځای سره نه پیل او پای ته رسي. موږ د دې جملې څخه علاوه یو تار یا کلمه هم چمتو کوو چې په جمله کې پلټلو ته اړتیا لرو. بیا موږ ته ویل کیږي چې د یوې کلیمې کوچنۍ شاخص بیرته راولو چې د لټون کلمه د هغې مخکینۍ په توګه لري. نو د ستونزې حل کولو لپاره یا موږ د ځایونو سره سم تارونه ویشلي. بیا یوازې ټکي وباسئ او وګورئ چې آیا اوسنی ټکی د لټون کلمې سره پیل کیږي. د دې عملیاتو ترسره کول په جاوا کې د ویشلو () او پیل کولو () کلیدي ټکو سره ساده دي.

د ستونزې حل کولو لپاره بله میتود دا دی چې په پیل کې جملو ته یو ځای اضافه کړئ. وروسته ، یا د موندلو () فنکشن وکاروئ یا د 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

جاوا کوډ

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) ، په دواړه حلونو کې موږ نوی صف یا نوی تار رامینځته کوو چې موږ ته ځای نیسي.