Bir sıra Leetcode həllində simli uyğunlaşdırma

Bir Array Leetcode Solution-da String Matching problemi bizə bir sıra simlər təqdim edir. Problem, bir başqasının alt simləri olan ipləri tapmağımızı xahiş edir sim girişdən. Yalnız bir qısa xatırlatma, bir alt simli simvolların hər iki ucundan silindikdən sonra qalan bir hissəsidir. Hər iki ucdan da 0 simvol silə bilərsiniz. Və silinən simvol sayının eyni olmasına ehtiyac yoxdur. Beləliklə, daha yaxşı başa düşmək üçün bir neçə nümunəyə nəzər salaq.

Pin

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

["as","hero"]

İzahat: Çıxış "kütlə" şəklində olduğu üçün "kimi" var. Eynilə, "qəhrəman" "superhero" nun bir hissəsidir. Beləliklə, sadəcə girişin alt sətirlərini tapdıq.

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

["et","code"]

İzahat: Bu nümunə alt simlərin eyni simdən ola biləcəyini göstərir. Buradakı kimi, çıxışdakı hər iki sətir də "leetcode" alt simlidir.

Bir sıra Leetcode həllində simli uyğunlaşma yanaşması

Problem, girişdən müəyyən bir şərti təmin edən simləri seçməyimizi istədi. Şərt budur ki, simli girişdə olan bir simli alt simli olmalıdır. Beləliklə, başqa bir simli alt sətir olan simləri tapmaq üçün bu prosesi simulyasiya etməyə çalışırıq. Qalan yeganə komplikasiya tətbiqetmədir. Beləliklə, nəticəmiz olacaq simləri izləmək üçün hashset və ya sıralanmamış xəritədən istifadə edirik. İth indeksindəki sətrin jth indeksindəki sətrin alt sətri olub olmadığını yoxlayan iki iç içə döngədən istifadə edirik və əksinə. C ++ dilində ikinci sətrin birinci arqumentin alt sətri olub olmadığını yoxlayan öz funksiyamızı yaratdıq. Java-da, () funksiyasından istifadə edərək asanlıqla tapıla bilər.

Array Leetcode həllində simli uyğunlaşdırma kodu

C ++ kodu

#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 kodu

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

Mürəkkəblik təhlili

Zaman mürəkkəbliyi

O (N ^ 2 * | S |), çünki giriş sətirlərinin sayından asılı olan iki iç içə döngə istifadə etdik. Sonra simli digər ehtiyacların alt simli olub olmadığını tapmaq üçün istifadə olunan funksiya O (| S |) vaxt.

Kosmik Mürəkkəblik

O (N), ən pis vəziyyətdə girişin hamısı çıxış ola bilər. Beləliklə kosmik mürəkkəblik xətti olur.