Решение Leetcode для кратчайшего завершения Word


Сложный уровень Легко
Часто спрашивают в Google
HashMap

Проблема Кратчайшее завершение слова Leetcode Solution гласит, что вам предоставляется номерной знак и массив строк ОС. Вам нужно найти самое короткое завершающее слово. Конкурирующее слово определяется как слово, имеющее все алфавиты в номерном знаке (без учета регистра). Частота букв в завершающем слове может быть больше, чем частота букв в автомобильном номере, но не может быть меньше. Итак, вам нужно найти самое короткое завершающее слово среди массива строк. Итак, давайте рассмотрим несколько примеров.

Решение Leetcode для кратчайшего завершения Word

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

Пояснение: Слово, указанное на номерном знаке, состоит из 2 с и 1 т. Слово из массива - «шаг», которое имеет только одно слово. Таким образом, «шаг» - не завершающее слово. Но в «шагах» есть 2 с, 1 т и другие буквы. Слово «шаги» удовлетворяет условию быть завершающим словом. И это также самое короткое завершающее слово. Таким образом, он возвращается в качестве ответа.

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

Объяснение: Все слова из массива являются завершающими словами. Но последние 3 слова - самые короткие завершающие слова. Среди самых коротких завершающих слов мы возвращаем первое самое короткое завершающее слово, то есть «вредитель».

Подход к решению Leetcode для кратчайшего завершения Word

Проблема Кратчайшее завершающее слово Leetcode Solution попросило нас найти самое короткое завершающее слово. В описании постановки задачи мы уже указали, что такое завершающее слово. Итак, найти кратчайшее завершающее слово. Во-первых, нам нужно найти частоту букв на номерном знаке. Эта частота не зависит от регистра букв. Затем мы пересекаем массив струн. И снова проделываем ту же операцию по нахождению частоты букв. Затем мы проверяем, является ли текущее слово завершающим словом. Если это так и размер текущего слова меньше, чем размер предыдущего завершающего слова, мы обновляем ответ. В итоге мы возвращаем самое короткое завершающее слово.

Код:

Код C ++ для кратчайшего завершения решения Leetcode Word

#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 Word

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), поскольку мы используем две HashMap постоянного размера. Объемная сложность для всего алгоритма постоянна.