Съвпадение на низовете в решение с масив Leetcode


Ниво на трудност Лесно
Често задавани в Амазонка
Низ

Проблемът String Matching в Array Leetcode Solution ни предоставя масив от низове. Проблемът ни изисква да намерим низовете, които са поднизове на някои други низ от входа. Само кратко напомняне, поднизът не е нищо друго освен част от низа, останала след премахване на символите от двата края. Можете също да премахнете 0 знака от двата края. И броят на премахнатите знаци не трябва да бъде еднакъв. Така че, за по-добро разбиране, нека разгледаме няколко примера.

Съвпадение на низовете в решение с масив Leetcode

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

Обяснение: Изходът има „като“, защото идва в „маса“. По подобен начин „герой“ е част от „супергерой“. По този начин ние просто намерихме поднизовете на входовете, които също са входни.

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

Обяснение: Този пример показва, че поднизовете могат да бъдат от същия низ. Както тук, и двата низа в изхода са поднизове на “leetcode”.

Подход за съвпадение на низове в Array Leetcode Solution

Проблемът ни помоли да изберем низовете от входа, които отговарят на конкретно условие. Условието е низът да бъде подниз от низ, който също е във входа. И така, ние се опитваме да симулираме този процес на намиране на низовете, които са поднизове на някой друг низ. Единственото усложнение, което остава, е изпълнението. Така че, ние използваме хешсет или неподредена карта, за да следим низовете, които ще служат като наш изход. Използваме два вложени цикъла, които проверяват дали низът в i-тия индекс е подниз от низ в jth индекс и обратно. В C ++ създадохме собствена функция, която проверява дали вторият низ е подниз от първия аргумент. В Java това може лесно да се намери с помощта на функцията contains ().

Код за съвпадение на низове в решение с 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

Анализ на сложността

Времева сложност

O (N ^ 2 * | S |), защото използвахме два вложени цикъла, които зависят от броя на входните низове. След това функцията, използвана за откриване дали низът е подниз от други нужди O (| S |) време.

Сложност на пространството

НА), в най-лошия случай целият вход може да бъде изходът. По този начин сложността на пространството е линейна.