குறுகிய முடித்தல் சொல் லீட்கோட் தீர்வு


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

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

குறுகிய முடித்தல் சொல் லீட்கோட் தீர்வு

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

விளக்கம்: உரிமத் தட்டில் கொடுக்கப்பட்டுள்ள சொல் 2 கள் மற்றும் 1 டி. வரிசையில் இருந்து வரும் சொல் “படி” என்பது ஒரே ஒன்றை மட்டுமே கொண்டுள்ளது. ஆகவே “படி” என்பது ஒரு முழுமையான சொல் அல்ல. ஆனால், “படிகள்” 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), நிலையான அளவு இரண்டு ஹாஷ்மேப்களை நாங்கள் பயன்படுத்துவதால். முழு வழிமுறைக்கான இட சிக்கலானது நிலையானது.