చిన్నదైన వర్డ్ లీట్‌కోడ్ పరిష్కారం


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది గూగుల్
హాష్ మ్యాప్

షార్టెస్ట్ కంప్లీటింగ్ వర్డ్ లీట్‌కోడ్ సొల్యూషన్ మీకు లైసెన్స్ ప్లేట్ మరియు ఓస్ తీగలను ఇస్తుందని పేర్కొంది. మీరు తక్కువ పూర్తి చేసిన పదాన్ని కనుగొనాలి. పోటీ పదాన్ని లైసెన్స్ ప్లేట్‌లోని అన్ని అక్షరాలను కలిగి ఉన్న పదంగా నిర్వచించారు (కేసు అస్పష్టత). పదం పూర్తి చేయడంలో అక్షరాల ఫ్రీక్వెన్సీ లైసెన్స్ ప్లేట్‌లోని అక్షరాల ఫ్రీక్వెన్సీ కంటే ఎక్కువగా ఉంటుంది, కానీ అది తక్కువగా ఉండకూడదు. కాబట్టి, మీరు తీగల శ్రేణిలో అతి తక్కువ పూర్తి చేసిన పదాన్ని కనుగొనాలి. కాబట్టి, కొన్ని ఉదాహరణలను పరిశీలిద్దాం.

చిన్నదైన వర్డ్ లీట్‌కోడ్ పరిష్కారం

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

వివరణ: లైసెన్స్ ప్లేట్‌లో ఇచ్చిన పదానికి 2 సె మరియు 1 టి ఉన్నాయి. శ్రేణి నుండి వచ్చిన పదం “దశ”, ఇది ఒకే ఒక్కదాన్ని కలిగి ఉంటుంది. అందువలన “దశ” అనేది పూర్తి చేసే పదం కాదు. కానీ, “దశలు” లో 2 సె, 1 టి మరియు ఇతర అక్షరాలు ఉన్నాయి. “స్టెప్స్” అనే పదం పూర్తి పదంగా ఉండటానికి పరిస్థితిని సంతృప్తిపరుస్తుంది. మరియు ఇది కూడా అతి తక్కువ పదం. అందువలన, ఇది సమాధానంగా తిరిగి ఇవ్వబడుతుంది.

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

వివరణ: శ్రేణిలోని అన్ని పదాలు పదాలను పూర్తి చేస్తున్నాయి. కానీ చివరి 3 పదాలు అతి తక్కువ పదాలు. పూర్తి చేసిన అతి తక్కువ పదాలలో, మేము “పెస్ట్” అనే మొదటి చిన్న పూర్తి పదాన్ని తిరిగి ఇస్తాము.

వర్డ్ లీట్‌కోడ్ సొల్యూషన్‌ను పూర్తి చేయడం కోసం అప్రోచ్

షార్టెస్ట్ కంప్లీటింగ్ వర్డ్ లీట్‌కోడ్ సొల్యూషన్ సమస్య అతి తక్కువ పూర్తి చేసిన పదాన్ని కనుగొనమని కోరింది. సమస్య స్టేట్మెంట్ యొక్క వివరణలో పూర్తి పదం ఏమిటో మేము ఇప్పటికే పేర్కొన్నాము. కాబట్టి, అతి తక్కువ పదం పూర్తి చేయడానికి. మొదట, లైసెన్స్ ప్లేట్‌లోని అక్షరాల ఫ్రీక్వెన్సీని మనం కనుగొనాలి. ఈ పౌన frequency పున్యం అక్షరం విషయంలో సున్నితంగా ఉంటుంది. అప్పుడు మేము ప్రయాణిస్తాము అమరిక తీగలను. అక్షరాల ఫ్రీక్వెన్సీని కనుగొనే అదే ఆపరేషన్‌ను మరోసారి చేస్తాము. ప్రస్తుత పదం పూర్తి పదమా అని మేము తనిఖీ చేస్తాము. ఇది మరియు ప్రస్తుత పదం యొక్క పరిమాణం మునుపటి పూర్తి చేసిన పదం కంటే తక్కువగా ఉంటే, మేము జవాబును నవీకరిస్తాము. చివరికి, మేము అతి తక్కువ పదం పూర్తి చేస్తాము.

కోడ్

చిన్నదైన వర్డ్ లీట్‌కోడ్ సొల్యూషన్ కోసం సి ++ కోడ్

#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), మేము స్థిరమైన పరిమాణంలోని రెండు హాష్ మ్యాప్‌లను ఉపయోగిస్తాము కాబట్టి. మొత్తం అల్గోరిథం కోసం స్థలం సంక్లిష్టత స్థిరంగా ఉంటుంది.