Решение за најкраток комплетиран збор за лек-код  


Ниво на тешкотија Лесно
Често прашувано во Google
алгоритми кодирање HashMap интервју интервју подготви LeetCode LeetCodeSolutions

Проблемот Решение за најкратко завршување на зборот 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 зборови се најкратки зборови кои завршуваат. Меѓу најкратките завршни зборови, го враќаме првиот најкраток завршен збор што е „штетник“.

Пристап за најкратко завршено решение за лек-код на зборови  

Проблемот Најкратко комплетирано решение за лек-код нè замоли да го најдеме најкраткиот збор за завршување. Веќе прецизиравме што е завршен збор, во описот на изјавата за проблемот. Значи, да го пронајдам најкраткиот збор што завршува. Прво, треба да ја најдеме фреквенцијата на буквите на регистарската табличка. Оваа фреквенција е нечувствителна на буквата. Потоа преминуваме преку низа на жиците. И уште еднаш ја извршуваме истата операција за наоѓање на фреквенцијата на буквите. Потоа проверуваме дали тековниот збор е завршен збор. Ако е, а големината на тековниот збор е помала од претходниот завршен збор, го ажурираме одговорот. На крајот, го враќаме најкраткиот завршен збор.

Видете исто така
Најдобро време за купување и продавање на акции со решение за ладење код за ладење

Код  

C ++ код за решение за летен код за најкратко завршување на зборот

#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 со постојана големина. Комплексноста на просторот за целиот алгоритам е постојана.

1