უმოკლეს ვადაში შევსების სიტყვა Leetcode ამოხსნა


Რთული ტური Easy
ხშირად ეკითხებიან Google
HashMap

პრობლემის უმოკლეს ვადაში დასრულების სიტყვა Leetcode Solution აცხადებს, რომ გეძლევათ სანომრე ნიშანი და OS სიმების მასივი. თქვენ უნდა იპოვოთ უმოკლესი დასრულების სიტყვა. კონკურენტ სიტყვად განისაზღვრება სიტყვა, რომელსაც აქვს ყველა ანბანი სანომრე ნიშანზე (მგრძნობიარე არ არის ასო). ასოების სიხშირე სიტყვის შევსებისას შეიძლება მეტი იყოს ვიდრე სანომრე ნიშანში არსებული ასოების სიხშირე, მაგრამ არ შეიძლება იყოს ნაკლები. ასე რომ, თქვენ უნდა იპოვოთ უმოკლესი დასრულების სიტყვა სტრიქონების მასივს შორის. მოდით, გადავხედოთ რამდენიმე მაგალითს.

უმოკლეს ვადაში შევსების სიტყვა Leetcode ამოხსნა

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 სიტყვა ყველაზე მოკლედ დასრულებული სიტყვებია. უმოკლეს დამამთავრებელ სიტყვებს შორის ვუბრუნებთ პირველ უმოკლეს დასრულების სიტყვას, რომელიც არის "მავნებელი".

მიდგომა უმოკლეს ვადაში შევსების სიტყვა Leetcode ამოხსნისთვის

პრობლემა უმოკლესი დასრულების სიტყვა Leetcode Solution- მა გვთხოვა იპოვოთ უმოკლესი დასრულების სიტყვა. ჩვენ უკვე დავაკონკრეტეთ რა არის დასრულების სიტყვა, პრობლემის დებულების აღწერაში. ასე რომ, უმოკლეს დამამთავრებელი სიტყვის პოვნა. პირველი, ჩვენ უნდა ვიპოვოთ ასოების სიხშირე სანომრე ნიშანზე. ეს სიხშირე მგრძნობიარე არ არის ასოთი. შემდეგ ჩვენ გავდივართ მასივი სიმების. კიდევ ერთხელ ვასრულებთ ასოების სიხშირის პოვნის იგივე ოპერაციას. შემდეგ ჩვენ ვამოწმებთ, არის თუ არა მიმდინარე სიტყვა დამამთავრებელი სიტყვა. თუ ეს არის და ამჟამინდელი სიტყვის ზომა უფრო მცირეა, ვიდრე წინა დასრულების სიტყვა, ჩვენ ვაახლებთ პასუხს. დასასრულს, ჩვენ ვუბრუნებთ უმოკლეს დასრულების სიტყვას.

კოდი

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

Java კოდი უმოკლეს დროში დასრულებული სიტყვის Leetcode ამოხსნისთვის

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), სადაც N არის სიმების მასივში სიტყვების რაოდენობა. ამრიგად, მთელ ალგორითმს აქვს ხაზოვანი დროის სირთულე.

სივრცის სირთულე

O (1), ვინაიდან ჩვენ ვიყენებთ მუდმივი ზომის ორ HashMap- ს. სივრცის სირთულე მთელი ალგორითმისთვის მუდმივია.