সংক্ষিপ্ততম কমপ্লিটিং ওয়ার্ড লেটকোড সলিউশন


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় গুগল
হ্যাশ মানচিত্র

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

সংক্ষিপ্ততম কমপ্লিটিং ওয়ার্ড লেটকোড সলিউশন

licensePlate = "1s3 PSt", words = ["step","steps","stripe","stepple"]
"steps"

ব্যাখ্যা: লাইসেন্স প্লেটে দেওয়া শব্দটির 2 টি এবং 1 টি রয়েছে। অ্যারে থেকে শব্দটি "পদক্ষেপ" যা কেবল একটিই আছে। সুতরাং "পদক্ষেপ" একটি সম্পূর্ণ শব্দ নয়। তবে, "পদক্ষেপগুলিতে" 2 টি, 1 টি এবং অন্যান্য অক্ষর রয়েছে। "পদক্ষেপ" শব্দটি একটি সম্পূর্ণ শব্দ হিসাবে শর্তটি সন্তুষ্ট করে। এবং এটি সংক্ষিপ্ত পরিপূর্ণ শব্দও। সুতরাং, এটি একটি উত্তর হিসাবে ফিরে আসে।

licensePlate = "1s3 456", words = ["looks","pest","stew","show"]
"pest"

ব্যাখ্যা: অ্যারে থেকে সমস্ত শব্দ শব্দ সম্পূর্ণ করছে। তবে সর্বশেষ 3 টি শব্দ হ'ল সংক্ষিপ্ত সমাপ্ত শব্দ। সংক্ষিপ্ত পরিপূর্ণ শব্দের মধ্যে আমরা প্রথম সংক্ষিপ্ত পরিপূর্ণ শব্দটি ফিরিয়ে দেব যা "কীটপতঙ্গ" is

সংক্ষিপ্ততম কমপ্লিটিং ওয়ার্ড লেটকোড সলিউশনের জন্য পন্থা

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

কোড

সংক্ষিপ্ততম কমপ্লিটিং ওয়ার্ড লেটকোড সলিউশন এর জন্য সি ++ কোড

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

string shortestCompletingWord(string licensePlate, vector<string>& words) {
    unordered_map<char, int> m;
    for(auto x: licensePlate){
        if((x>='A' && x<='Z') || (x>='a' && x<='z'))
            m[tolower(x)]++;
    }
    string answer = string(16, 'a');
    for(auto word: words){
        unordered_map<char, int> mm;
        for(auto x: word){
            if((x>='A' && x<='Z') || (x>='a' && x<='z'))
                mm[tolower(x)]++;
        }
        bool cant = false;
        for(char i='a';i<='z';i++)
            if(mm[i] < m[i])
                cant = true;
        if(!cant){
            if(word.length() < answer.length())
                answer = word;
        }
    }
    return answer;
}

int main(){
    string licensePlate = "1s3 PSt";
    vector<string> words({"step","steps","stripe","stepple"});
    cout<<shortestCompletingWord(licensePlate, words);
}
steps

সংক্ষিপ্ততম শব্দ সম্পন্ন শব্দ লেটকোড সমাধানের জন্য জাভা কোড

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static String shortestCompletingWord(String licensePlate, String[] words) {
       HashMap <Character, Integer> m = new HashMap<Character, Integer>();
        int licensePlateSize = licensePlate.length();
        for(int i=0;i<licensePlateSize;i++){
            char x = licensePlate.charAt(i);
            if((x>='A' && x<='Z') || (x>='a' && x<='z'))
                m.put(Character.toLowerCase(x), m.containsKey(Character.toLowerCase(x)) ? (m.get(Character.toLowerCase(x)) + 1) : 1);
        }
        String answer = "aaaaaaaaaaaaaaaa";
        for(String word: words){
            HashMap<Character, Integer> mm = new HashMap<Character, Integer>();
            int wordSize = word.length();
            for(int i=0;i<wordSize;i++){
                char x = word.charAt(i);
                if((x>='A' && x<='Z') || (x>='a' && x<='z'))
                    mm.put(Character.toLowerCase(x), mm.containsKey(Character.toLowerCase(x)) ? (mm.get(Character.toLowerCase(x)) + 1) : 1);
            }
            boolean cant = false;
            for(char i='a';i<='z';i++){
                int a = m.containsKey(i) ? m.get(i) : 0;
                int b = mm.containsKey(i) ? mm.get(i) : 0;
                if(b < a)
                    cant = true;
            }
            if(cant == false){
                if(word.length() < answer.length())
                    answer = word;
            }
        }
        return answer; 
    }
    
  public static void main (String[] args) throws java.lang.Exception{
    String licensePlate = "1s3 PSt";
      String words[] = {"step","steps","stripe","stepple"};
      System.out.print(shortestCompletingWord(licensePlate, words));
  }
}
steps

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

সময় জটিলতা

চালু), যেখানে এন হল স্ট্রিংগুলির অ্যারের শব্দের সংখ্যা। সুতরাং পুরো অ্যালগরিদমের লিনিয়ার সময় জটিলতা রয়েছে।

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

ও (1), যেহেতু আমরা ধ্রুব আকারের দুটি হ্যাশম্যাপ ব্যবহার করি। পুরো অ্যালগরিদমের জন্য স্থান জটিলতা ধ্রুবক।