Ən qısa tamamlama sözü Leetcode həlli

Çətinlik səviyyəsi Asan
Tez-tez soruşulur google
alqoritmlər kodlaşdırma HashMap müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutionsBaxılıb 69

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Ən qısa şəkildə tamamlanan Word Leetcode Solution problemi sizə bir plaka və bir sıra os simli verildiyini bildirir. Ən qısa tamamlayan sözü tapmaq lazımdır. Rəqib bir söz, plaka içindəki bütün əlifbaları olan bir söz olaraq təyin edilir (vəziyyətə həssas deyil). Sözü tamamlayan hərflərin sayı avtomobil nömrəsindəki hərflərin tezliyindən çox ola bilər, lakin daha az ola bilməz. Beləliklə, dizələr sırası arasında ən qısa tamamlayan söz tapmaq lazımdır. Beləliklə, bir neçə nümunəyə nəzər salaq.

Ən qısa tamamlama sözü Leetcode həlliPin

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

İzahat: Avtomobil nömrəsində verilmiş söz 2 s və 1 t-dir. Dizidən gələn söz yalnız bir dənə olan "addım" dır. Beləliklə, "addım" tamamlayan bir söz deyil. Ancaq "addımlar" ın 2 s, 1 ton və digər hərfləri var. "Addımlar" sözü tamamlayıcı bir söz olma şərtini təmin edir. Həm də ən qısa tamamlayan sözdür. Beləliklə, cavab olaraq geri qaytarılır.

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

İzahat: Dizidəki bütün sözlər sözləri tamamlayır. Ancaq son 3 söz ən qısa tamamlayan sözlərdir. Ən qısa tamamlama sözləri arasında ilk ən qısa tamamlama sözü “zərərverici” olaraq qaytarırıq.

Word Leetcode həllinin ən qısa tamamlanması üçün yanaşma

Problemin ən qısa tamamlanması Word Leetcode Solution ən qısa tamamlama sözü tapmağımızı istədi. Tamamlayıcı bir sözün nə olduğunu artıq problem ifadəsinin təsvirində qeyd etmişik. Beləliklə, ən qısa tamamlayan söz tapmaq. Əvvəlcə plakadakı hərflərin tezliyini tapmalıyıq. Bu tezlik məktubun vəziyyətinə həssasdır. Sonra üstündən keçirik array simli. Və bir daha hərflərin tezliyini tapmaqla eyni əməliyyatı həyata keçiririk. Sonra mövcud sözün tamamlayan bir söz olub olmadığını yoxlayırıq. Varsa və cari sözün ölçüsü əvvəlki tamamlama sözündən kiçikdirsə, cavabı yeniləyirik. Sonda ən qısa tamamlayan sözü qaytarırıq.

Kodu

Qısa Tamamlama Word Leetcode Həlli üçün C ++ kodu

#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

Qisa Tamamlanan Word Leetcode Həlli üçün Java kodu

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N), burada N - dizələr sırasındakı sözlərin sayı. Beləliklə, bütün alqoritm xətti zaman mürəkkəbliyinə malikdir.

Kosmik Mürəkkəblik

O (1), çünki sabit ölçülü iki HashMap istifadə edirik. Bütün alqoritm üçün yer mürəkkəbliyi sabitdir.

Crack Sistemi Dizayn Müsahibələri
Translate »
1