String Matching- ը զանգվածի Leetcode լուծման մեջ


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Amazon
String

String Matching in a Array Leetcode Solution լուծումը մեզ տրամադրում է տողերի զանգված: Խնդիրը մեզ խնդրում է գտնել այն տողերը, որոնք ինչ-որ այլի ենթալարեր են լարային մուտքագրումից: Ուղղակի արագ հիշեցում, ենթատողը ոչ այլ ինչ է, քան լարի մի մասը, որը մնում է երկու ծայրերից նիշերը հեռացնելուց հետո: Երկու ծայրերից կարող եք նաև հեռացնել 0 նիշ: Եվ հանված նիշերի քանակը պետք չէ նույնը լինել: Այսպիսով, ավելի լավ հասկանալու համար եկեք նայենք մի քանի օրինակների:

String Matching- ը զանգվածի Leetcode լուծման մեջ

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

Բացատրություն. Արդյունքն ունի «as», քանի որ այն գալիս է «զանգվածի»: Նմանապես, «հերոսը» «սուպերհերոսի» մի մասն է: Այսպիսով, մենք պարզապես հայտնաբերեցինք մուտքերի ենթատողերը, որոնք նույնպես մուտքագրում են:

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

Բացատրություն. Այս օրինակը ցույց է տալիս, որ ենթատողերը կարող են լինել նույն լարից: Ինչպես այստեղ, ելքի երկու տողերն էլ «leetcode» - ի ենթալար են:

Ringանգվածային համընկնումի մոտեցում զանգվածի Leetcode լուծման մեջ

Խնդիրը մեզ խնդրեց մուտքից ընտրել տողերը, որոնք բավարարում են որոշակի պայման: Պայմանն այն է, որ լարը պետք է լինի լարի ենթալար, որը նույնպես մուտքագրման մեջ է: Այսպիսով, մենք փորձում ենք մոդելավորել այս գործընթացը `գտնելու այն տողերը, որոնք ինչ-որ այլ տողի ենթալար են: Միակ բարդությունը, որ մնում է, իրականացումն է: Այսպիսով, մենք օգտագործում ենք խեշեթ կամ չպատվիրված քարտեզ ՝ հետագծելու համար այն տողերը, որոնք ծառայելու են որպես մեր արդյունքը: Մենք օգտագործում ենք երկու տեղադրված օղակ, որոնք ստուգում են ՝ արդյոք ith ինդեքսում տողը jth ինդեքսում տողի ենթալար է և հակառակը: C ++ - ում մենք ստեղծեցինք մեր սեփական գործառույթը, որը ստուգում է, արդյոք երկրորդ տողը առաջին արգումենտի ենթալար է: Java- ում դա կարելի է հեշտությամբ գտնել ՝ օգտագործելով περιέχει () գործառույթը:

Ringանգվածային համընկնման կոդ զանգվածի Leetcode լուծման մեջ

C ++ ծածկագիր

#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

Java կոդ

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

Բարդության վերլուծություն

Timeամանակի բարդությունը

Ո (N ^ 2 * | Ս |), քանի որ մենք օգտագործել ենք երկու տեղադրված օղակ, որոնք կախված են մուտքային լարերի քանակից: Այնուհետև գործառույթն օգտագործվում է պարզելու համար, թե արդյոք տողը այլ կարիքների ենթալար է Ո (| Ս |) Թեմա.

Տիեզերական բարդություն

ՎՐԱ), վատագույն դեպքում ամբողջ մուտքը կարող է լինել արդյունքը: Այսպիսով, տարածության բարդությունը գծային է: