Array Leetcode шийдэлд мөр тохирох


Хэцүү байдлын түвшин Easy
Байнга асуудаг Амазоны
String

Array Leetcode шийдэл дэх String Matching гэсэн асуудал нь бидэнд олон тооны мөрүүдийг өгдөг. Асуудал нь биднээс бусад мөрний мөрүүдийг олохыг хүсдэг мөр оролтоос. Зүгээр л хурдан сануулахад дэд мөр нь юу ч биш, тэмдэгтүүдийг хоёр төгсгөлөөс нь арилгасны дараа үлдсэн хэсэг юм. Та хоёр төгсгөлөөс 0 тэмдэгт хасаж болно. Устгасан тэмдэгтүүдийн тоо ижил байх шаардлагагүй. Тиймээс илүү сайн ойлгохын тулд цөөн хэдэн жишээг авч үзье.

Array Leetcode шийдэлд мөр тохирох

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

Тайлбар: Гаралт нь "масстай" байдаг тул гарц нь "as" байна. Үүнтэй адилаар "баатар" бол "супер баатар" -ын нэг хэсэг юм. Тиймээс бид оролтын дэд мөрүүдийг олсон болно.

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

Тайлбар: Энэ жишээнээс харахад дэд мөрүүд нэг мөрөөс байж болно. Энд байгаа шиг гаралтын хоёр мөр нь хоёулаа "leetcode" дэд мөр юм.

Массивын Leetcode шийдлийн мөрийг тааруулах арга

Асуудал нь оролтоос тодорхой нөхцлийг хангасан мөрүүдийг сонгохыг биднээс хүссэн. Нөхцөл нь мөр нь оролтонд байгаа мөрийн дэд мөр байх ёстой. Тиймээс бид бусад мөрийн дэд мөрийг олох энэ үйл явцыг дууриахыг хичээдэг. Үлдсэн цорын ганц хүндрэл бол хэрэгжилт юм. Тиймээс бид hashset эсвэл эрэмбэлэгдээгүй газрын зургийг ашиглан бидний гаралт болох мөрүүдийг хянах болно. Бид ith индекс дэх мөр нь jth индекс дэх мөрийн дэд мөр мөн эсэхийг шалгадаг хоёр үүрлэсэн гогцоог ашигладаг. C ++ хэл дээр бид хоёр дахь мөр нь эхний аргументийн дэд мөр мөн эсэхийг шалгадаг өөрийн функцийг бий болгосон. Java дээр үүнийг () функцийг ашиглан хялбархан олж болно.

Array 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 |) цаг хугацаа.

Сансрын нарийн төвөгтэй байдал

O (N), хамгийн муу тохиолдолд бүхэлдээ оролт байж болно. Тиймээс орон зайн нарийн төвөгтэй байдал нь шугаман юм.