Bütün sözlərin birləşdirildiyi alt sətir Leetcode Həlli

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Çiy kərpic Amazon alma Bloomberg Facebook google microsoft Kahin
Hashing Sürüşmə pəncərə SimBaxılıb 22

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

The Bütün sözlərin birləşdirildiyi alt sətir LeetCode Həlli – “Bütün sözlərin birləşdirilməsi ilə alt sətir” sətir verildiyini bildirir s və simli bir sıra sözləri hər sözün olduğu yer eyni uzunluq. Hamısını geri qaytarmalıyıq başlanğıc indeksləri sözlərdə hər bir sözün tam olaraq bir dəfə, hər hansı bir ardıcıllıqla, heç bir müdaxilə simvolu olmadan birləşməsi olan alt sətirin.

Misal:

Input:  s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]

Explanation:

  • 0 indeksindən başlayan alt sətir: “barfoo”.
  • İndeks 9-dan başlayan alt sətir: “foobar”.
  • Beləliklə, cavab [0, 9]-dur.
Input:  s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []

Explanation:

  • Tələb olunan alt sətir yoxdur.

Yanaşma

Idea:

  1. Bu problemi həll etmək üçün əsas fikir istifadə etməkdir HashSet or Sürüşmə pəncərə.
  2. Hər sözün uzunluğu sabit olduğundan, biz təkrarlayacağıq sabit uzunluqlu L giriş sətirinə daxil edin və bütün fərqli simvolların tezliklərinin dəqiq uyğunluğunu tapmaq üçün sürüşmə pəncərə texnikasından istifadə edin, sonra cari pəncərənin başlanğıc indeksini saxlayırıq.
  3. Birincisi, sətirlərin tezliklərini HashSet-də saxlayın.
  4. İndi [0, L – 1] diapazonunda hər i üçün sabit uzunluqlu L üçün təkrarlayın.
  5. Nə vaxt tapsaq a alt sətir HashSet-də baş verməyən L uzunluğunda, o zaman söz sətirləri massivində mövcud olan bütün sözləri ehtiva edən tələb olunan alt sətirə sahib ola bilmərik, buna görə də bütün dəyərləri sıfırlayırıq.
  6. Əks halda, HashSet-imizdəki cari alt sətirin tezliyini artırın və bu dəyər istədiyiniz tezlikə uyğun gələndə uyğunluq sayını artıracağıq.
  7. Cari alt sətirin tezliyi istənilən tezlikdən çox olduqda, biz pəncərənin başlanğıc indeksini qısaldacağıq və uyğun olaraq uyğunluq sayını dəyişdirəcəyik.
  8. Hər zaman uyğunluq sayı istədiyiniz matç sayına bərabərdir, biz cari pəncərənin başlanğıc indeksini saxlayacağıq.

Kodu

Bütün sözlərin birləşdirildiyi alt sətir Leetcode C++ Həlli:

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        unordered_map <string, int> occ;
        for(auto& word : words){
            occ[word]++;
        }
        
        vector <int> ans;
        int sz = occ.size();
        
        int n = s.length(), m = words.size(), len = words.back().length();
        for(int i=0; i<len; i++){
            int start = i, match = 0;
            unordered_map <string, int> now;
            for(int end=i+len-1; end<n; end+=len){
                string str = s.substr(end-len+1, len);
                if(!occ.count(str)){
                    now.clear();
                    
                    match = 0;
                    start = end + 1;
                }
                else{
                    now[str]++;
                    if(now[str] == occ[str]){
                        match++;
                    }
                    while(now[str] > occ[str]){
                        if(now[s.substr(start, len)] == occ[s.substr(start, len)]){
                            match--;
                        }

                        now[s.substr(start, len)]--;

                        if(now[s.substr(start, len)] == 0){
                            now.erase(s.substr(start, len));
                        }

                        start += len;
                    }
                    
                    if(match == sz){
                        ans.push_back(start);
                    }
                }
            }
        }
        
        return ans;
    }
};

Bütün sözlərin birləşdirildiyi alt sətir Leetcode Java Həlli:

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        int N = s.length();
        List<Integer> indexes = new ArrayList<Integer>(s.length());
        if (words.length == 0) {
            return indexes;
        }
        int M = words[0].length();
        if (N < M * words.length) {
            return indexes;
        }
        int last = N - M + 1;

        Map<String, Integer> mapping = new HashMap<String, Integer>(words.length);
        int [][] table = new int[2][words.length];
        int failures = 0, index = 0;
        for (int i = 0; i < words.length; ++i) {
            Integer mapped = mapping.get(words[i]);
            if (mapped == null) {
                ++failures;
                mapping.put(words[i], index);
                mapped = index++;
            }
            ++table[0][mapped];
        }

        int [] smapping = new int[last];
        for (int i = 0; i < last; ++i) {
            String section = s.substring(i, i + M);
            Integer mapped = mapping.get(section);
            if (mapped == null) {
                smapping[i] = -1;
            } else {
                smapping[i] = mapped;
            }
        }

        for (int i = 0; i < M; ++i) {
            int currentFailures = failures; 
            int left = i, right = i;
            Arrays.fill(table[1], 0);

            while (right < last) {
                while (currentFailures > 0 && right < last) {
                    int target = smapping[right];
                    if (target != -1 && ++table[1][target] == table[0][target]) {
                        --currentFailures;
                    }
                    right += M;
                }
                while (currentFailures == 0 && left < right) {
                    int target = smapping[left];
                    if (target != -1 && --table[1][target] == table[0][target] - 1) {
                        int length = right - left;

                        if ((length / M) ==  words.length) {
                            indexes.add(left);
                        }
                        ++currentFailures;
                    }
                    left += M;
                }
            }

        }
        return indexes;
    }
}

Bütün sözlərin birləşməsi ilə alt sətir üçün mürəkkəblik təhlili Leetcode həlli

Zamanın mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O(N*L + M) bütün giriş massivini iki dəfə keçdiyimiz üçün (sürüşmə pəncərəsi texnikası) və hər mövqe üçün L uzunluğunda alt sətir çıxarırıq, burada N = s sətirinin ölçüsü, L = hər sözün uzunluğu, M = massivin ölçüsü sözlərdən.

Kosmik Mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O(M).

Crack Sistemi Dizayn Müsahibələri
Translate »