सबसे छोटा पूरा शब्द Leetcode Solution


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

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

सबसे छोटा पूरा शब्द Leetcode Solution

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

स्पष्टीकरण: लाइसेंस प्लेट में दिए गए शब्द में 2 s और 1 t है। सरणी से शब्द "चरण" है जिसमें केवल एक ही है। इस प्रकार "चरण" एक पूर्ण शब्द नहीं है। लेकिन, "चरणों" में 2 एस, 1 टी और अन्य अक्षर हैं। शब्द "कदम" एक पूरा होने की शर्त को संतुष्ट करता है। और यह सबसे छोटा पूरा शब्द भी है। इस प्रकार, यह एक उत्तर के रूप में वापस आ जाता है।

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

स्पष्टीकरण: सरणी से सभी शब्द शब्दों को पूरा कर रहे हैं। लेकिन अंतिम 3 शब्द सबसे कम पूरा करने वाले शब्द हैं। कम से कम पूरा करने वाले शब्दों में, हम पहला सबसे कम पूरा करने वाला शब्द है जो "कीट" है।

सबसे छोटा शब्द लेटकोड समाधान के लिए दृष्टिकोण

समस्या सबसे कम पूरा करने वाला शब्द लेटकोड सॉल्यूशन ने हमें सबसे छोटा पूरा करने वाला शब्द खोजने को कहा। हमने पहले ही निर्दिष्ट कर दिया है कि समस्या कथन के विवरण में एक पूरा होने वाला शब्द क्या है। तो, कम से कम पूरा करने वाले शब्द को खोजने के लिए। सबसे पहले, हमें लाइसेंस प्लेट पर अक्षरों की आवृत्ति का पता लगाना होगा। यह आवृत्ति पत्र के मामले के प्रति असंवेदनशील है। तो हम पर पार सरणी तार के। और एक बार फिर हम अक्षरों की आवृत्ति खोजने का एक ही ऑपरेशन करते हैं। फिर हम जांचते हैं कि क्या वर्तमान शब्द एक पूरा होने वाला शब्द है। यदि यह है और वर्तमान शब्द का आकार पिछले पूर्ण होने वाले शब्द से छोटा है, तो हम उत्तर को अपडेट करते हैं। अंत में, हम सबसे छोटा पूरा शब्द वापस करते हैं।

कोड

सी + कोड शॉर्ट लेटेस्ट वर्ड लिटकोड सॉल्यूशन के लिए

#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

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

समय जटिलता

पर), जहाँ N स्ट्रिंग्स के सरणी में शब्दों की संख्या है। इस प्रकार पूरे एल्गोरिथ्म में रैखिक समय की जटिलता है।

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

ओ (1), चूँकि हम निरंतर आकार के दो HashMaps का उपयोग करते हैं। संपूर्ण एल्गोरिथ्म के लिए अंतरिक्ष जटिलता निरंतर है।