تطبیق رشته در یک راه حل کد آرایه


سطح دشواری ساده
اغلب در آمازون
رشته

مسئله String Matching in a Array Leetcode Solution آرایه ای از رشته ها را برای ما فراهم می کند. مشکل از ما می خواهد رشته هایی را که زیر رشته برخی دیگر هستند ، پیدا کنیم رشته از ورودی فقط یک یادآوری سریع ، زیر رشته چیزی نیست جز بخشی از رشته باقیمانده پس از حذف کاراکترها از هر دو انتها. همچنین می توانید 0 حرف را از هر دو انتها حذف کنید. و تعداد کاراکترهای حذف شده نیازی نیست که یکسان باشد. بنابراین ، برای درک بهتر ، اجازه دهید نگاهی به چند نمونه بیندازیم.

تطبیق رشته در یک راه حل کد آرایه

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

توضیح: خروجی "as" دارد زیرا در "mass" می آید. به همین ترتیب ، "قهرمان" بخشی از "ابرقهرمان" است. بنابراین ، ما به سادگی زیر رشته های ورودی هایی را که ورودی نیز هستند ، پیدا کردیم.

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

توضیح: این مثال نشان می دهد که زیر رشته ها می توانند از یک رشته باشند. مانند اینجا ، هر دو رشته در خروجی زیر رشته "leetcode" هستند.

رویکرد تطبیق رشته ای در یک راه حل کد کد آرایه

این مشکل از ما خواست که رشته هایی را از ورودی انتخاب کنیم که شرایط خاصی را تأمین می کنند. شرط اینست که رشته باید زیر رشته ای باشد که در ورودی نیز باشد. بنابراین ، ما سعی می کنیم این فرآیند را برای یافتن رشته هایی که زیر رشته برخی رشته های دیگر هستند ، شبیه سازی کنیم. تنها عارضه ای که باقی می ماند اجرای آن است. بنابراین ، برای پیگیری رشته هایی که به عنوان خروجی ما عمل می کنند ، از هاشست یا نقشه غیر مرتب استفاده می کنیم. ما از دو حلقه تو در تو استفاده می کنیم که بررسی می کند رشته در شاخص ith یک رشته فرعی از رشته در شاخص jth است و بالعکس. در C ++ ، تابع خود را ایجاد کردیم که بررسی می کند رشته دوم زیر رشته آرگومان اول است یا خیر. در جاوا با استفاده از تابع () به راحتی می توان این مورد را یافت.

کد تطبیق رشته در یک راه حل کد کد آرایه

کد 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

کد جاوا

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 |) زمان.

پیچیدگی فضا

بر)، در بدترین حالت کل ورودی می تواند خروجی باشد. بنابراین پیچیدگی فضا خطی است.