सब भन्दा छिटो पूरा हुने शब्द लीटकोड समाधान


कठिनाई तह सजिलो
बारम्बार सोधिन्छ गुगल
हशम्याप

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

सब भन्दा छिटो पूरा हुने शब्द लीटकोड समाधान

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

स्पष्टीकरण: लाइसेन्स प्लेटमा दिइएको शब्दसँग २ s र १ टी छ। एर्रेबाट शब्द "चरण" हो जससँग केवल एक मात्र छ। यसैले "चरण" एक पूरा शब्द होईन। तर, "चरणहरू" सँग २ s, १ टी, र अन्य अक्षरहरू छन्। शब्द "चरण" शर्त एक पूरा शब्द हुन संतुष्ट। र यो पनि छोटो पूर्ण गर्ने शब्द हो। यसरी, यो उत्तरको रूपमा फिर्ता हुन्छ।

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

स्पष्टीकरण: एर्रेबाट सबै शब्दहरूले शब्दहरू पूरा गर्दैछ। तर अन्तिम words शब्दहरू छोटकरीमा पूर्ण हुने शब्दहरू हुन्। सब भन्दा छोटो पूर्ण गर्ने शब्दहरू मध्ये हामी पहिलो छोटो पूर्ण हुने शब्द फर्काउँछौं जुन "कीरा" हो।

सब भन्दा छोटो पूर्ण गर्ने शब्द लेटकोड समाधानको लागि दृष्टिकोण

समस्या सबैभन्दा छोटो पूरा गर्ने शब्द लेटकोड समाधानले हामीलाई छोटो छोटो पूरा गर्ने शब्द फेला पार्न भन्यो। हामीले समस्याको विवरणको वर्णनमा, एक समाप्त हुने शब्द के हो भनेर निर्दिष्ट गरिसक्यौं। त्यसो भए, छोटो पूर्ण गर्ने शब्द फेला पार्न। पहिले, हामीले लाइसेन्स प्लेटमा अक्षरहरूको फ्रिक्वेन्सी फेला पार्नु पर्छ। यो फ्रिक्वेन्सी पत्र को मामला को प्रति संवेदनहीन छ। त्यसोभए हामी पार गर्छौं array तारको। र फेरि हामी अक्षरहरूको फ्रिक्वेन्सी फेला पार्न उही अपरेशन गर्दछौं। त्यसो भए हामीले जाँच गर्‍यौं कि हालको शब्द एक पूरा शब्द हो कि होइन। यदि यो हो र हालको शब्दको आकार अघिल्लो पूरा हुने शब्द भन्दा सानो छ भने हामी उत्तर अपडेट गर्दछौं। अन्तमा, हामी सब भन्दा छोटो पूरा गर्ने शब्द फर्काउँछौं।

कोड

C ++ कोड छोटो कम पूरा हुने शब्द Leetcode समाधानको लागि

#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

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

समय जटिलता

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

ठाउँ जटिलता

O (१), किनकि हामी स्थिर आकारको दुई ह्यासम्यापहरू प्रयोग गर्दछौं। सम्पूर्ण एल्गोरिथ्मको लागि ठाउँ जटिलता स्थिर छ।