अ‍ॅरे लीटकोड सोल्यूशनमध्ये स्ट्रिंग मॅचिंग


अडचण पातळी सोपे
वारंवार विचारले ऍमेझॉन
अक्षरमाळा

अ‍ॅरे लीटकोड सोल्यूशनमध्ये स्ट्रिंग मॅचिंगची समस्या आपल्याला तारांचे अ‍ॅरे प्रदान करते. समस्या आम्हाला काही इतरांच्या सबस्ट्रिंग असलेल्या तार शोधण्यास सांगते स्ट्रिंग इनपुट वरून फक्त एक द्रुत स्मरणपत्र, एक स्ट्रिंग दोन्ही टोकांवरील वर्ण काढून टाकल्यानंतर उर्वरित तारांच्या भागाशिवाय काही नाही. आपण दोन्ही टोकांमधून 0 वर्ण देखील काढू शकता. आणि काढलेल्या वर्णांची संख्या समान असणे आवश्यक नाही. तर, अधिक चांगल्या प्रकारे समजण्यासाठी आपण काही उदाहरणे पाहू या.

अ‍ॅरे लीटकोड सोल्यूशनमध्ये स्ट्रिंग मॅचिंग

words = ["mass","as","hero","superhero"]
["as","hero"]

स्पष्टीकरणः आउटपुट मध्ये "as" आहे कारण ते "मास" मध्ये येते. त्याचप्रमाणे “हिरो” हा “सुपरहीरो” चा भाग आहे. अशाप्रकारे आम्हाला फक्त इनपुटची सबस्ट्रिंग्ज सापडली जी देखील इनपुट आहेत.

words = ["leetcode","et","code"]
["et","code"]

स्पष्टीकरणः हे उदाहरण दर्शविते की सबस्ट्रिंग्स समान स्ट्रिंगमधून असू शकतात. येथे प्रमाणे आउटपुट मधील दोन्ही स्ट्रिंग्स “लीटकोड” च्या सबस्ट्रिंग आहेत.

अ‍ॅरे लीटकोड सोल्यूशनमध्ये स्ट्रिंग मॅचिंगसाठी दृष्टीकोन

समस्येने आम्हाला विशिष्ट शर्ती पूर्ण करणार्‍या इनपुटमधून तार निवडण्यास सांगितले. अट अशी आहे की स्ट्रिंग स्ट्रिंगचा सबस्ट्रिंग असावा जो इनपुटमध्ये देखील असेल. तर, आम्ही स्ट्रिंग शोधण्याच्या या प्रक्रियेचे अनुकरण करण्याचा प्रयत्न करतो ज्या इतर स्ट्रिंगच्या सब्स्ट्रिंग आहेत. फक्त गुंतागुंत उरली आहे ती अंमलबजावणीची. तर आम्ही आपल्या आऊटपुट म्हणून काम करेल अशा तारांचा मागोवा ठेवण्यासाठी हॅशसेट किंवा अनऑर्डर नकाशा वापरतो. आम्ही दोन नेस्टेड लूप वापरतो जी तपासते की आयथ इंडेक्समधील स्ट्रिंग स्ट्रिंगची स्ट्रिंग स्ट्रेंथची स्ट्रिंग स्ट्रिंग आहे आणि त्याउलट उलट आहे. सी ++ मध्ये, आम्ही आमचे स्वतःचे फंक्शन तयार केले आहे जे तपासते की दुसरी स्ट्रिंग पहिल्या वितर्कातील सबस्ट्रिंग आहे किंवा नाही. जावा मध्ये, हे () फंक्शन वापरून सहजपणे आढळू शकते.

अ‍ॅरे लीटकोड सोल्यूशनमध्ये स्ट्रिंग मॅचिंगसाठी कोड

सी ++ कोड

#include <bits/stdc++.h>
using namespace std;

bool isSubstr(string a, string b){
    int n = a.size(), m = b.size();
    for(int i=0;i<=n-m;i++){
        if(a.substr(i, m) == b)
            return true;
    }
    return false;
}

vector<string> stringMatching(vector<string>& words) {
    unordered_set<string> tmp;
    int n = words.size();
    for(int i=0;i<n-1;i++){
        string curWord = words[i];
        for(int j=i+1;j<n;j++){
            string nextWord = words[j];
            if(isSubstr(curWord, nextWord))
                tmp.insert(nextWord);
            if(isSubstr(nextWord, curWord))
                tmp.insert(curWord);
        }
    }
    return vector<string>(tmp.begin(), tmp.end());
}

int main(){
    vector<string> input({"mass","as","hero","superhero"});
    vector<string> v = stringMatching(input);
    for(auto x: v)
        cout<<x<<" ";
}
hero as

जावा कोड

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static List<String> stringMatching(String[] words) {
        HashSet<String> tmp = new HashSet<>();
        
        int n = words.length;
        for(int i = 0; i<n-1; i++) {
            String curWord = words[i];
            for(int j = i+1; j<n; j++) {
                String nextWord = words[j];
                if(curWord.contains(nextWord))
                    tmp.add(nextWord);
                if(nextWord.contains(curWord))
                    tmp.add(curWord);
            }
        }
        
        return new ArrayList<String>(tmp);
    }
    
  public static void main (String[] args) throws java.lang.Exception{
    String[] words = {"mass","as","hero","superhero"};
    List<String> list = stringMatching(words);
    for(String x: list)
      System.out.print(x+" ");
  }
}
hero as

गुंतागुंत विश्लेषण

वेळ गुंतागुंत

ओ (एन ^ 2 * | एस |), कारण आम्ही दोन नेस्टेड लूप वापरलेले आहेत जे इनपुट स्ट्रिंगच्या संख्येवर अवलंबून आहेत. नंतर स्ट्रिंग इतर गरजा एक सबस्ट्रिंग आहे की नाही हे शोधण्यासाठी वापरलेले फंक्शन ओ (| एस |) वेळ

स्पेस कॉम्प्लेक्सिटी

ओ (एन), सर्वात वाईट परिस्थितीत संपूर्ण इनपुट आउटपुट असू शकते. अशा प्रकारे स्पेस कॉम्प्लेक्सिटी रेखीय असते.