একটি অ্যারে লেটকোড সমাধানে স্ট্রিং ম্যাচিং


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় মর্দানী স্ত্রীলোক
স্ট্রিং

অ্যারে লেটকোড সলিউশনে স্ট্রিং ম্যাচিংয়ের সমস্যাটি আমাদের স্ট্রিংগুলির একটি অ্যারে সরবরাহ করে। সমস্যাটি আমাদেরকে স্ট্রিংগুলি অনুসন্ধান করতে বলে যা কিছু অন্যের সাবস্ট্রিংগুলি স্ট্রিং ইনপুট থেকে কেবলমাত্র একটি দ্রুত অনুস্মারক, উভয় প্রান্ত থেকে অক্ষর অপসারণের পরে স্ট্রিংয়ের কিছু অংশ বাদে কেবল একটি সাবস্ট্রিং কিছুই নয়। আপনি উভয় প্রান্ত থেকে 0 টি অক্ষরও মুছে ফেলতে পারেন। এবং সরানো অক্ষরের সংখ্যা একই হওয়ার দরকার নেই। সুতরাং, আরও ভাল বোঝার জন্য আসুন আমরা কয়েকটি উদাহরণ ঘুরে দেখি।

একটি অ্যারে লেটকোড সমাধানে স্ট্রিং ম্যাচিং

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

ব্যাখ্যা: আউটপুটটির "হিসাবে" রয়েছে কারণ এটি "ভর" এ আসে। একইভাবে, "নায়ক" "সুপারহিরো" এর একটি অংশ। সুতরাং, আমরা কেবল ইনপুট যে ইনপুট হয় তা সাবস্ট্রিংগুলি খুঁজে পেয়েছি।

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

ব্যাখ্যা: এই উদাহরণটি দেখায় যে সাবস্ট্রিংগুলি একই স্ট্রিং থেকে হতে পারে। এখানে যেমন, আউটপুট উভয় স্ট্রিং "লেটকোড" এর সাবস্ট্রিং হয়।

অ্যারে লেটকোড সলিউশনে স্ট্রিং ম্যাচিংয়ের জন্য অ্যাপ্রোচ

সমস্যাটি আমাদের একটি নির্দিষ্ট শর্ত পূরণ করে এমন ইনপুট থেকে স্ট্রিংগুলি তুলতে বলেছে। শর্তটি হ'ল স্ট্রিংটি স্ট্রিংয়ের একটি স্ট্রিং হতে হবে যা ইনপুটটিতেও থাকে। সুতরাং, আমরা স্ট্রিংগুলি খুঁজে পেতে এই প্রক্রিয়াটি অনুকরণ করার চেষ্টা করি যা কিছু অন্যান্য স্ট্রিংয়ের সাবস্ট্রিং থাকে। কেবলমাত্র জটিলতা রয়ে গেছে বাস্তবায়ন। সুতরাং, আমরা আমাদের আউটপুট হিসাবে পরিবেশন করবে এমন স্ট্রিংগুলির ট্র্যাক রাখতে হ্যাশसेट বা আনর্ডার করা মানচিত্র ব্যবহার করি। আমরা দুটি নেস্টেড লুপ ব্যবহার করি যা পরীক্ষা করে দেখি যে ith ইনডেক্সে স্ট্রিংটি jth সূচক এবং তার বিপরীতে স্ট্রিংয়ের একটি স্ট্রিং। সি ++ তে আমরা আমাদের নিজস্ব ফাংশন তৈরি করেছি যা দ্বিতীয় স্ট্রিংটি প্রথম আর্গুমেন্টের সাবস্ট্রিং কিনা তা পরীক্ষা করে। জাভাতে, এটি () ফাংশন ব্যবহার করে সহজেই পাওয়া যায়।

অ্যারে লেটকোড সমাধানে স্ট্রিং ম্যাচিংয়ের জন্য কোড

সি ++ কোড

#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 * | এস |), কারণ আমরা দুটি নেস্টেড লুপ ব্যবহার করেছি যা ইনপুট স্ট্রিংয়ের সংখ্যার উপর নির্ভরশীল। তারপরে স্ট্রিংটি অন্য প্রয়োজনের একটি স্ট্রিং কিনা তা অনুসন্ধান করতে ব্যবহৃত ফাংশনটি ও (| এস |) সময়।

স্পেস জটিলতা ity

চালু), সবচেয়ে খারাপ ক্ষেত্রে পুরো ইনপুট আউটপুট হতে পারে। সুতরাং স্থান জটিলতা রৈখিক হয়।