Բառի Leetcode լուծման ամենակարճ լուծումը


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Google
HashMap

Խնդրի ամենակարճ լրացման Leetcode Solution- ի խնդրում նշվում է, որ ձեզ տրվում է պետհամարանիշ և os տողերի զանգված: Դուք պետք է գտնեք ամենակարճ ավարտող բառը: Մրցակցող բառը բնութագրվում է որպես բառ, որն ունի պետհամարանիշի բոլոր այբուբենները (դեպքերի համար անզգա): Բառի լրացման մեջ տառերի հաճախականությունը կարող է ավելի մեծ լինել, քան համարանիշի տառերի հաճախությունը, բայց չի կարող պակաս լինել: Այսպիսով, տողերի շարքում պետք է գտնել ամենակարճ լրացնող բառը: Այսպիսով, եկեք դիտենք մի քանի օրինակներ:

Բառի Leetcode լուծման ամենակարճ լուծումը

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

Բացատրություն. Համարանիշում տրված բառը ունի 2 վ և 1 տ: Rayանգվածից ստացված բառը «քայլ» է, որն ունի միայն մեկ: Այսպիսով, «քայլը» ավարտական ​​բառ չէ: Բայց «քայլերն» ունեն 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

Բարդության վերլուծություն

Timeամանակի բարդություն

ՎՐԱ), որտեղ N- ը տողերի զանգվածում բառերի քանակն է: Այսպիսով, ամբողջ ալգորիթմը ունի գծային ժամանակի բարդություն:

Տիեզերական բարդություն

O (1), քանի որ մենք օգտագործում ենք հաստատուն չափի երկու HashMaps: Տիեզերական բարդությունն ամբողջ ալգորիթմի համար հաստատուն է: