ஒரு வரிசை லீட்கோட் தீர்வில் சரம் பொருத்தம்


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அமேசான்
சரம்

ஒரு வரிசை லீட்கோட் தீர்வில் சரம் பொருந்தும் சிக்கல் எங்களுக்கு ஒரு வரிசை சரங்களை வழங்குகிறது. வேறு சிலவற்றின் மூலக்கூறுகளாக இருக்கும் சரங்களைக் கண்டுபிடிக்க சிக்கல் கேட்கிறது சரம் உள்ளீட்டிலிருந்து. ஒரு விரைவான நினைவூட்டல், ஒரு மூலக்கூறு என்பது இரு முனைகளிலிருந்தும் எழுத்துக்களை அகற்றிய பின் மீதமுள்ள சரத்தின் ஒரு பகுதியைத் தவிர வேறில்லை. இரு முனைகளிலிருந்தும் 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

சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

O (N ^ 2 * | S |), ஏனெனில் உள்ளீட்டு சரங்களின் எண்ணிக்கையைப் பொறுத்து இரண்டு உள்ளமை சுழல்களைப் பயன்படுத்தியுள்ளோம். சரம் மற்ற தேவைகளுக்கு அடி மூலக்கூறு என்பதை அறிய பயன்படுத்தப்படும் செயல்பாடு ஓ (| எஸ் |) நேரம்.

விண்வெளி சிக்கலானது

ஓ (என்), மிக மோசமான நிலையில் முழு உள்ளீடும் வெளியீடாக இருக்கலாம். இதனால் விண்வெளி சிக்கலானது நேரியல் ஆகும்.