সবচেয়ে ছোট চরিত্রের লেটকোড সমাধানের ফ্রিকোয়েন্সি দ্বারা স্ট্রিংগুলির তুলনা করুন


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় গুগল আকাশবাণী
বিন্যাস স্ট্রিং

ক্ষুদ্রতর অক্ষর লেটকোড সমাধানের ফ্রিকোয়েন্সি দ্বারা স্ট্রিংগুলির তুলনা করে সমস্যাটি বলে যে আমরা একটি ফাংশন এফ (গুলি) একটি খালি না করে সংজ্ঞায়িত করি স্ট্রিং এর মতো যে চ (গুলি) স্ট্রিংয়ের ক্ষুদ্রতম অক্ষরের ফ্রিকোয়েন্সি সমান। তারপরে আমাদের কিছু শব্দ এবং কিছু প্রশ্ন দেওয়া হয়। প্রতিটি ক্যোয়ারির জন্য, আমাদের f (শব্দ)> চ (ক্যোয়ারী_শব্দ) এর শব্দের সংখ্যা খুঁজে বের করতে হবে। তারপরে আমাদের ভেক্টর বা অ্যারে হিসাবে সমস্ত প্রশ্নের উত্তর ফিরিয়ে দিতে হবে। সুতরাং, সমাধানের গভীরে ডুব দেওয়ার আগে আসুন কয়েকটি উদাহরণ দেখে নেওয়া যাক।

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

ব্যাখ্যা: f ("zaaaz") = 3, কারণ ক্ষুদ্রতম চরিত্রটি 'এ' যার ফ্রিকোয়েন্সি 3 এর সমান হয়, যখন f ("সিবিডি") = 1। সুতরাং, আমাদের কেবল একটি শব্দ রয়েছে যা f (i) আছে )> চ (ক্যোয়ারী_ওয়ার্ড)।

সবচেয়ে ছোট চরিত্রের লেটকোড সমাধানের ফ্রিকোয়েন্সি দ্বারা স্ট্রিংগুলির তুলনা করুন

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

ব্যাখ্যা: সুতরাং, প্রদত্ত সমস্ত শব্দের জন্য সংজ্ঞায়িত ফাংশনটির মান গণনার পরে। আমরা f (“a”) = 1, f (“aa”) = 2, f (“aaa”) = 3, f (“aaa”) = 4 খুঁজে পেয়েছি ”এ বর্ণিত শব্দের জন্য ফাংশনের মান মূল্যায়ন করার পরে অনুসন্ধানসমূহ, আমরা f ("বিবিবি") = 3, চ ("সিসি") = ২ পাই। সুতরাং, আমরা দেখতে পাই যে চ ("বিবিবি") শব্দের জন্য আমাদের একটি শব্দ আছে "আআআ" যার ফাংশনের মান রয়েছে ৩. এর চেয়ে বড় greater

সবচেয়ে ছোট চরিত্রের লেটকোড সমাধানের ফ্রিকোয়েন্সি অনুসারে স্ট্রিংগুলির তুলনা করার পদ্ধতির জন্য

সমস্যাটি স্ট্রিংগুলির তুলনা ক্ষুদ্রতম অক্ষর লেটকোড সমাধানের ফ্রিকোয়েন্সি দ্বারা কোয়েরি শব্দের জন্য ফাংশনের মানের চেয়ে আরও বেশি সংজ্ঞায়িত ফাংশনটির জন্য ইনপুট থেকে এমন শব্দের সংখ্যা জানতে বলে। নন-খালি স্ট্রিংগুলির উপরে সংজ্ঞায়িত ফ (গুলি) স্ট্রিংয়ের ক্ষুদ্রতম অক্ষরের ফ্রিকোয়েন্সি সমান। সুতরাং, প্রথমে আমরা সমস্ত ক্যোয়ারী শব্দের জন্য ফাংশনের মান খুঁজে পাই। সমস্ত ইনপুট শব্দের জন্য আমরা একই কাজ করি। আমরা একটি অতিরিক্ত অ্যারেও তৈরি করি যা ফাংশনের মান সমান শব্দের সংখ্যা সঞ্চয় করে। এই অ্যারেটি ধ্রুব সময়ে আমাদের প্রশ্নের উত্তর খুঁজতে সহায়তা করবে। অ্যারের প্রতিটি সূচক i শব্দের সংখ্যাকে বোঝায় যেটির ফাংশন মান = i।

ফাংশন মান মূল্যায়ন এবং তাদের আমাদের অস্থায়ী অ্যারে সংরক্ষণের পরে। আমরা অস্থায়ী অ্যারের প্রত্যয় যোগফলটি গ্রহণ করি যে প্রতিটি সূচক এখন i এর সমান ফাংশন মানযুক্ত মোট শব্দের সংখ্যাকে সংরক্ষণ করে। এখন আমরা প্রতিটি ক্যোয়ারী শব্দের উত্তর সহজভাবে একটি অ্যারে বা ভেক্টরে সংরক্ষণ করি এবং তা ফিরে পাই।

সবচেয়ে ছোট চরিত্রের লেটকোড সমাধানের ফ্রিকোয়েন্সি অনুসারে স্ট্রিংগুলির তুলনা করার জন্য কোড

সি ++ কোড

#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

জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (প্রশ্ন + এন), যেহেতু আমাদের সকল শব্দের জন্য ফাংশন মান গণনা করতে হবে এবং শব্দের দৈর্ঘ্য 10 এর চেয়ে কম বা সমান।

স্পেস জটিলতা ity

ও (প্রশ্ন), যেহেতু আমরা উত্তর সংরক্ষণ করতে একটি অ্যারে এবং অস্থায়ী ব্যবহারের জন্য 10 মাপের একটি অতিরিক্ত অ্যারে তৈরি করি। স্থান জটিলতাও লিনিয়ার।