सबसे छोटे अक्षर लेकोडकोड समाधान की आवृत्ति द्वारा स्ट्रिंग्स की तुलना करें


कठिनाई स्तर आसान
में अक्सर पूछा गूगल ओरेकल
ऐरे तार

समस्या सबसे छोटे अक्षर लेकोडकोड सॉल्यूशन की फ्रीक्वेंसी की स्ट्रिंग्स की तुलना करती है, बताती है कि हम एक फंक्शन को गैर-खाली पर परिभाषित करते हैं। स्ट्रिंग s ऐसा कि f (s) स्ट्रिंग में सबसे छोटे वर्ण की आवृत्ति के बराबर है। फिर हमें कुछ शब्द और कुछ प्रश्न दिए जाते हैं। प्रत्येक प्रश्न के लिए, हमें ऐसे शब्दों की संख्या ज्ञात करने की आवश्यकता है जैसे कि f (शब्द)> f (query_word)। फिर हमें सभी प्रश्नों के उत्तर को एक वेक्टर या एक सरणी के रूप में वापस करना होगा। तो, समाधान में गहराई से गोता लगाने से पहले, आइए कुछ उदाहरणों पर एक नज़र डालते हैं।

queries = ["cbd"], words = ["zaaaz"]
[1]

स्पष्टीकरण: f ("zaaaz") = 3, क्योंकि सबसे छोटा वर्ण 'a' है जिसकी आवृत्ति 3 के बराबर है, जबकि f ("cbd") = 1. तो, हमारे पास केवल एक ही शब्द है जिसका f है (i) )> f (query_word)।

सबसे छोटे अक्षर लेकोडकोड समाधान की आवृत्ति द्वारा स्ट्रिंग्स की तुलना करें

queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"]
[1,2]

स्पष्टीकरण: तो, सभी दिए गए शब्दों के लिए परिभाषित फ़ंक्शन के मूल्य की गणना के बाद। हम एफ ("ए") = 1, एफ ("एए") = 2, एफ ("एएए") = 3, एफ ("आ आ") = 4 पाते हैं। 3. दिए गए शब्दों के लिए फ़ंक्शन के मूल्य का मूल्यांकन करने के बाद प्रश्न, हम f ("bbb") = 2, f ("cc") = 3 पाते हैं। तो, फिर हम पाते हैं कि शब्द f ("bbb") के लिए, हमारे पास एक एकल शब्द "आआआ" है जिसका फ़ंक्शन मान है XNUMX से अधिक। इसी तरह, "cc" शब्द के लिए, हमारे पास "आआ", "आआआ" शब्द हैं जिनका अधिक कार्य मूल्य है।

सबसे छोटे अक्षर लेकोडकोड समाधान की आवृत्ति द्वारा स्ट्रिंग्स की तुलना करने के लिए दृष्टिकोण

समस्या की तुलना स्ट्रिंग्स की आवृत्ति से होती है सबसे छोटे अक्षर लेटकोड सॉल्यूशन में इनपुट से ऐसे शब्दों की संख्या को खोजने के लिए कहा गया है, जिनका फ़ंक्शन परिभाषित मूल्य के लिए फ़ंक्शन के मान से अधिक है। गैर-रिक्त तारों पर परिभाषित फ़ंक्शन f (s) एक स्ट्रिंग में सबसे छोटे वर्ण की आवृत्ति के बराबर है। तो, पहले, हम सभी क्वेरी शब्दों के लिए फ़ंक्शन का मान पाते हैं। हम सभी इनपुट शब्दों के लिए ऐसा ही करते हैं। हम एक अतिरिक्त सरणी भी बनाते हैं जो उन शब्दों की संख्या को संग्रहीत करता है जिनके पास फ़ंक्शन मान i के बराबर है। यह सरणी हमें निरंतर समय में प्रश्नों के उत्तर खोजने में मदद करेगी। एरे के प्रत्येक इंडेक्स I में उन शब्दों की संख्या है जो फ़ंक्शन मान = i है।

फ़ंक्शन मान के मूल्यांकन और उन्हें हमारे अस्थायी सरणी में संग्रहीत करने के बाद। हम अस्थायी सरणी का प्रत्यय लेते हैं, जैसे कि प्रत्येक सूचकांक अब कुल ऐसे शब्दों को संग्रहीत करता है जिनका फ़ंक्शन मान अधिक या बराबर होता है। अब हम प्रत्येक क्वेरी शब्द के उत्तर को एक ऐरे या वेक्टर में स्टोर करते हैं और उसे वापस करते हैं।

सबसे छोटे अक्षर लेकोडकोड समाधान की आवृत्ति द्वारा स्ट्रिंग्स की तुलना के लिए कोड

C ++ कोड

#include <bits/stdc++.h>
using namespace std;

vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words) {
    vector<int> q;
    for(auto x: queries){
        int f[26] = {0};
        int mn = 26;
        for(auto y: x){
            f[y-'a']++;
            mn = min(mn, y-'a');
        }
        q.push_back(f[mn]);
    }

    int fr[12];memset(fr, 0, sizeof fr);
    for(auto x: words){
        int f[26] = {0};
        int mn = 26;
        for(auto y: x){
            f[y-'a']++;
            mn = min(mn, y-'a');
        }
        fr[f[mn]]++;
    }
    for(int i=9;i>=0;i--)
        fr[i] += fr[i+1];
    vector<int> ans;
    for(auto x: q){
        ans.push_back(fr[x+1]);
    }
    return ans;
}

int main(){
    vector<string> queries = {"bbb","cc"};
    vector<string> words = {"a","aa","aaa","aaaa"};

    vector<int> answer = numSmallerByFrequency(queries, words);
    for(auto x: answer)
        cout<<x<<" ";
}
1 2

जावा कोड

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
    public static int[] numSmallerByFrequency(String[] queries, String[] words) {
        ArrayList<Integer> q = new ArrayList<Integer>();
        for(String x: queries){
            int[] f = new int[26];
            for(int i=0;i<26;i++)
                f[i] = 0;
            int mn = 26;
            int sz = x.length();
            for(int i=0;i<sz;i++){
                int y = x.charAt(i);
                f[y-'a']++;
                mn = Math.min(mn, y-'a');
            }
            q.add(f[mn]);
        }
 
        int[] fr = new int[12];
        for(int i=0;i<12;i++)
            fr[i] = 0;
        for(String x: words){
            int[] f = new int[26];
            for(int i=0;i<26;i++)
                f[i] = 0;
            int mn = 26;
            int sz = x.length();
            for(int i=0;i<sz;i++){
                int y = x.charAt(i);
                f[y-'a']++;
                mn = Math.min(mn, y-'a');
            }
            fr[f[mn]]++;
        }
        for(int i=9;i>=0;i--)
            fr[i] += fr[i+1];
        int[] ans = new int[queries.length];
        for(int i=0;i<q.size();i++){
            ans[i] = (fr[q.get(i)+1]);
        }
        return ans;
    }
 
  public static void main (String[] args) throws java.lang.Exception
  {
    String[] queries = {"bbb","cc"};
      String[] words = {"a","aa","aaa","aaaa"};
 
      int[] answer = numSmallerByFrequency(queries, words);
      for(int x: answer)
          System.out.print(x+" ");
  }
}
1 2

जटिलता विश्लेषण

समय जटिलता

O (Q + N), क्योंकि हमें सभी शब्दों के लिए फ़ंक्शन मान की गणना करनी है और शब्दों की लंबाई भी 10. से कम या बराबर है। इस प्रकार समय जटिलता रैखिक है।

अंतरिक्ष जटिलता

O (Q), क्योंकि हम अस्थायी उपयोग के लिए उत्तर और आकार 10 के अतिरिक्त सरणी को संग्रहीत करने के लिए एक सरणी बनाते हैं। अंतरिक्ष की जटिलता भी रैखिक है।