Bütün sözlərin birləşməsi ilə alt sətir

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Amazon DE Şou
Hashing Sim İki işarəBaxılıb 102

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.

Bütün sözlər probleminin birləşməsi ilə alt sətirdə a sim s və siyahı hər biri eyni uzunluqda olan bir çox sözdən ibarətdir. Siyahıdakı bütün sözlərin birləşdirilməsinin nəticəsi ola biləcək alt sətrin başlanğıc indeksini istənilən qaydada çap edin.

Pin

Bütün sözlərin birləşməsi ilə sətiralma izahı

S = “capcodthecodcap” sətri və verilən siyahı L = [“cap”, “cod”] qoyulsun

Verilən siyahının bütün sözlərini birləşdirin. Verilən siyahının bütün sözlərini birləşdirən bütün mümkün birləşmələr -

  • capcod
  • codcap

İndi verilən sətirdə birləşdirilmiş sətirlərin başlanğıc indeksini axtarın.

Verilən sətirdə “capcod” alt sətrinin başlanğıc indeksicapcodkod kodu ”0-dur.

Verilən sətirdə “codcap” alt sətrinin başlanğıc indeksi “capcodthecodcap”9-dur.

Buna görə çıxış 0 və 9 olacaqdır.

misal

Input: 

s = "capcodthecodcap"

L = [“qapaq”, “cod”]

Çıxış:

0 9

Input: 

s = "heythejenna"

L = ["hey", "the"]

Çıxış:

0

Alqoritm

  1. N uzunluğunda s sətri və verilən sətrin uzunluğu ilə eyni sözlərin siyahısını başlayın.
  2. Bir xəritəni və müvəqqəti bir xəritəni başlatın.
  3. Verilən siyahının bütün sözlərinin birləşməsinə bərabər olan uzunluqdakı bütün alt sətirlərdən keçin.
  4. Bütün mümkün alt simlərdən istifadə edərək yeni xəritəni köhnə xəritə ilə əlaqələndirin.
  5. Substring sözlərinin yeni xəritədə olub olmadığını yoxlayın, sayını 1 azaldın, əks halda döngəni qırın.
  6. Yeni xəritədən keçin və bütün sözlərin sayının 0-dan az olub olmadığını yoxlayın, siyahı / massiv res.
  7. Geri qaytarılan siyahıdan / massivdən keçin və içindəki bütün dəyərləri çap edin.

Bütün sözlərin birləşməsi ilə alt simli tapmaq üçün C ++ proqramı

#include <bits/stdc++.h> 
using namespace std; 
  
vector<int> Substring(string s, const vector<string>& L){ 
  
    int size = L[0].size(); 
  
    int count = L.size(); 
  
    int length = size * count; 
  
    vector<int> res; 
  
    if(length>s.size()) 
        return res; 
  
    unordered_map<string, int> hash_map; 
  
    for(int i=0; i<count; i++)  
        hash_map[L[i]]++;     
  
    for(int i=0; i<=s.size()-length; i++) { 
        unordered_map<string, int> temp_hash_map(hash_map); 
  
        int j = i,c=count; 
  
        while(j<i+length){ 
  
            string word = s.substr(j, size); 
  
  
            if(hash_map.find(word) == hash_map.end()||temp_hash_map[word]==0) 
                break; 
  
            else{ 
                temp_hash_map[word]--;
                c--;
            }  
            j += size; 
        } 
       
        if(c == 0) 
            res.push_back(i); 
    } 
  
    return res; 
} 
  
int main(){ 
    string s = "capcodthecodcap"; 
    vector<string> L = { "cap", "cod" }; 
    vector<int> indices = Substring(s, L); 
    for(int i=0; i<indices.size(); i++) 
        cout<<indices[i]<<" "; 
    return 0; 
}
0 9

Bütün sözlərin birləşməsi ilə alt sətir tapmaq üçün Java Proqramı

import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.HashMap; 
import java.util.List;

class sub{
    
    public static ArrayList<Integer>Substring(String s, final List<String> L){ 
  
        int size = L.get(0).length(); 
         
        int count = L.size(); 
  
        int length = size * count; 
  
        ArrayList<Integer> res = new ArrayList<Integer>(); 
        int n = s.length(); 
          
        if(length > n){ 
            return res; 
        } 
  
        HashMap<String, Integer> hashMap = new HashMap<String, Integer>(); 
  
        for(String word : L){ 
            hashMap.put(word, hashMap.getOrDefault(word, 0) + 1); 
        } 
  
          
        for(int i=0; i<=n-length; i++){ 
            HashMap<String, Integer> tempMap = (HashMap<String, Integer>) hashMap.clone(); 
            int j = i, c = count; 
              
            while(j<i+length){ 
                String word = s.substring(j, j+size); 
              
                if(!hashMap.containsKey(word) || tempMap.get(word) == 0){ 
                    break; 
                }  
                  
                else{ 
                    tempMap.put(word, tempMap.get(word) - 1); 
                    c--; 
                } 
                j += size; 
            } 
              
            if(c == 0){ 
                res.add(i); 
            } 
  
        } 
        return res; 
    } 
  
    public static void main(String[] args){ 
        String s = "capcodthecodcap"; 
        ArrayList<String> L = new ArrayList<>(Arrays.asList("cap", "cod")); 
        ArrayList<Integer> indices = Substring(s, L); 
        for(Integer i : indices){
            System.out.print(i+" "); 
        } 
    }
}
0 9

Zamanın mürəkkəbliyi: O (nk) * k (n sətrin uzunluğu, k bütün siyahı sözləri birləşdikdən sonra ümumi uzunluqdur)

References

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