சிறிய எழுத்துக்குறி லீட்கோட் தீர்வின் அதிர்வெண் மூலம் சரங்களை ஒப்பிடுக


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது கூகிள் ஆரக்கிள்
அணி சரம்

சிறிய எழுத்துக்குறி லீட்கோட் தீர்வின் அதிர்வெண் மூலம் சரங்களை ஒப்பிடுவதில் சிக்கல், காலியாக இல்லாத ஒரு செயல்பாடு f (களை) வரையறுக்கிறோம் என்று கூறுகிறது சரம் கள் (f) என்பது சரத்தின் மிகச்சிறிய எழுத்தின் அதிர்வெண்ணுக்கு சமம். பின்னர் எங்களுக்கு சில சொற்களும் சில கேள்விகளும் வழங்கப்படுகின்றன. ஒவ்வொரு வினவலுக்கும், f (சொற்கள்)> f (வினவல்_ச்சொல்) போன்ற சொற்களின் எண்ணிக்கையை நாம் கண்டுபிடிக்க வேண்டும். எல்லா வினவல்களுக்கும் ஒரு திசையன் அல்லது ஒரு வரிசையாக நாம் பதிலை வழங்க வேண்டும். எனவே, தீர்வுக்கு ஆழமாக டைவ் செய்வதற்கு முன், சில எடுத்துக்காட்டுகளைப் பார்ப்போம்.

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

விளக்கம்: f (“zaaaz”) = 3, ஏனெனில் மிகச்சிறிய எழுத்துக்குறி 3 க்கு சமமான அதிர்வெண் கொண்ட 'a' ஆகும், அதே சமயம் f (“cbd”) = 1. எனவே, f (i )> f (வினவல்_ச்சொல்).

சிறிய எழுத்துக்குறி லீட்கோட் தீர்வின் அதிர்வெண் மூலம் சரங்களை ஒப்பிடுக

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

விளக்கம்: எனவே, கொடுக்கப்பட்ட அனைத்து சொற்களுக்கும் வரையறுக்கப்பட்ட செயல்பாட்டின் மதிப்பைக் கணக்கிட்ட பிறகு. நாம் f (“a”) = 1, f (“aa”) = 2, f (“aaa”) = 3, f (“aaaa”) = 4. இல் கொடுக்கப்பட்டுள்ள சொற்களுக்கான செயல்பாட்டின் மதிப்பை மதிப்பிட்ட பிறகு வினவல்கள், f (“பிபிபி”) = 3, எஃப் (“சிசி”) = 2. எனவே, எஃப் (“பிபிபி”) என்ற சொல்லுக்கு, செயல்பாட்டு மதிப்பைக் கொண்ட “ஆஆஆ” என்ற ஒற்றை சொல் இருப்பதைக் காண்கிறோம். 3 ஐ விட அதிகமாக. இதேபோல், “சிசி” என்ற சொல்லுக்கு, “ஆஆ”, “ஆஆஆ” என்ற சொற்கள் உள்ளன, அவை அதிக செயல்பாட்டு மதிப்பைக் கொண்டுள்ளன.

மிகச்சிறிய எழுத்துக்குறி லீட்கோட் தீர்வின் அதிர்வெண் மூலம் சரங்களை ஒப்பிடுவதற்கான அணுகுமுறை

சிக்கல் சிறிய எழுத்துக்குறி லீட்கோட் தீர்வின் அதிர்வெண் மூலம் சரங்களை ஒப்பிடுங்கள் வினவல் சொற்களுக்கான செயல்பாட்டின் மதிப்பை விட வரையறுக்கப்பட்ட செயல்பாட்டிற்கான மதிப்பைக் கொண்ட உள்ளீட்டிலிருந்து சொற்களின் எண்ணிக்கையைக் கண்டுபிடிக்க கேட்கிறது. வெற்று அல்லாத சரங்களில் வரையறுக்கப்பட்ட f (கள்) செயல்பாடு ஒரு சரத்தின் மிகச்சிறிய எழுத்தின் அதிர்வெண்ணுக்கு சமம். எனவே, முதலில், அனைத்து வினவல் சொற்களுக்கும் செயல்பாட்டின் மதிப்பைக் காண்கிறோம். எல்லா உள்ளீட்டு சொற்களுக்கும் நாங்கள் அவ்வாறே செய்கிறோம். 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

சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

O (Q + N), எல்லா சொற்களுக்கும் செயல்பாட்டு மதிப்பை நாம் கணக்கிட வேண்டும், மேலும் சொற்களின் நீளமும் 10 ஐ விட குறைவாகவோ அல்லது சமமாகவோ இருக்கும். இதனால் நேர சிக்கலானது நேரியல்.

விண்வெளி சிக்கலானது

ஓ (கே), பதிலைச் சேமிக்க ஒரு வரிசையையும், தற்காலிக பயன்பாட்டிற்காக 10 அளவு கூடுதல் வரிசையையும் உருவாக்குவதால். விண்வெளி சிக்கலானது நேரியல் ஆகும்.