748. Shortest Completing Word

LeetCode easy original: C# #array #csharp #easy #hash-table #leetcode #string

Le texte du problème est traduit du russe pour la langue sélectionnée. Le code reste inchangé.

LeetCode Static

Вам дан entier tableau nums, в котором наибольшее entier уникально. Определите, является ли наибольший element tableauа по крайней мере в два раза больше всех остальных чисел в tableauе. Если да, то return индекс самого большого elementа, в противном случае return -1.

Exemple:

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

Output: "steps"

C# solution

correspondant/original

using System;
using System.Collections.Generic;
public class Solution {
    public string ShortestCompletingWord(string licensePlate, string[] words) {
        var licenseCount = GetCharCount(licensePlate);
        string result = null;
        foreach (var word in words) {
            if (IsCompletingWord(word, licenseCount)) {
                if (result == null || word.Length < result.Length) {
                    result = word;
                }
            }
        }
        return result;
    }
    private Dictionary<char, int> GetCharCount(string s) {
        var count = new Dictionary<char, int>();
        foreach (var c in s.ToLower()) {
            if (char.IsLetter(c)) {
                count[c] = count.GetValueOrDefault(c, 0) + 1;
            }
        }
        return count;
    }
    private bool IsCompletingWord(string word, Dictionary<char, int> licenseCount) {
        var wordCount = new Dictionary<char, int>();
        foreach (var c in word) {
            wordCount[c] = wordCount.GetValueOrDefault(c, 0) + 1;
        }
        foreach (var entry in licenseCount) {
            if (!wordCount.ContainsKey(entry.Key) || wordCount[entry.Key] < entry.Value) {
                return false;
            }
        }
        return true;
    }
}

C++ solution

brouillon automatique, à relire avant soumission

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public string ShortestCompletingWord(string licensePlate, vector<string> words) {
        var licenseCount = GetCharCount(licensePlate);
        string result = null;
        foreach (var word in words) {
            if (IsCompletingWord(word, licenseCount)) {
                if (result == null || word.size() < result.size()) {
                    result = word;
                }
            }
        }
        return result;
    }
    private unordered_map<char, int> GetCharCount(string s) {
        var count = new unordered_map<char, int>();
        foreach (var c in s.ToLower()) {
            if (char.IsLetter(c)) {
                count[c] = count.GetValueOrDefault(c, 0) + 1;
            }
        }
        return count;
    }
    private bool IsCompletingWord(string word, unordered_map<char, int> licenseCount) {
        var wordCount = new unordered_map<char, int>();
        foreach (var c in word) {
            wordCount[c] = wordCount.GetValueOrDefault(c, 0) + 1;
        }
        foreach (var entry in licenseCount) {
            if (!wordCount.count(entry.Key) || wordCount[entry.Key] < entry.Value) {
                return false;
            }
        }
        return true;
    }
}

Java solution

correspondant/original

import java.util.*;

public class Solution {
    public String shortestCompletingWord(String licensePlate, String[] words) {
        Map<Character, Integer> licenseCount = getCharCount(licensePlate);
        
        String result = null;
        for (String word : words) {
            if (isCompletingWord(word, licenseCount)) {
                if (result == null || word.length() < result.length()) {
                    result = word;
                }
            }
        }
        return result;
    }
    
    private Map<Character, Integer> getCharCount(String s) {
        Map<Character, Integer> count = new HashMap<>();
        for (char c : s.toLowerCase().toCharArray()) {
            if (Character.isLetter(c)) {
                count.put(c, count.getOrDefault(c, 0) + 1);
            }
        }
        return count;
    }
    
    private boolean isCompletingWord(String word, Map<Character, Integer> licenseCount) {
        Map<Character, Integer> wordCount = new HashMap<>();
        for (char c : word.toCharArray()) {
            wordCount.put(c, wordCount.getOrDefault(c, 0) + 1);
        }
        for (Map.Entry<Character, Integer> entry : licenseCount.entrySet()) {
            if (wordCount.getOrDefault(entry.getKey(), 0) < entry.getValue()) {
                return false;
            }
        }
        return true;
    }
}

JavaScript solution

correspondant/original

var shortestCompletingWord = function(licensePlate, words) {
    function getCharCount(s) {
        const count = {};
        for (const char of s.toLowerCase()) {
            if (/[a-z]/.test(char)) {
                count[char] = (count[char] || 0) + 1;
            }
        }
        return count;
    }

    const licenseCount = getCharCount(licensePlate);

    function isCompletingWord(word, licenseCount) {
        const wordCount = {};
        for (const char of word) {
            wordCount[char] = (wordCount[char] || 0) + 1;
        }
        for (const [char, cnt] of Object.entries(licenseCount)) {
            if ((wordCount[char] || 0) < cnt) {
                return false;
            }
        }
        return true;
    }

    let result = null;
    for (const word of words) {
        if (isCompletingWord(word, licenseCount)) {
            if (result === null || word.length < result.length) {
                result = word;
            }
        }
    }
    return result;
};

Python solution

correspondant/original

import collections

def shortestCompletingWord(licensePlate, words):
    def get_char_count(s):
        count = collections.Counter()
        for char in s:
            if char.isalpha():
                count[char.lower()] += 1
        return count
    
    license_count = get_char_count(licensePlate)
    
    def is_completing_word(word, license_count):
        word_count = collections.Counter(word)
        for char, cnt in license_count.items():
            if word_count[char] < cnt:
                return False
        return True
    
    result = None
    for word in words:
        if is_completing_word(word, license_count):
            if result is None or len(word) < len(result):
                result = word
    return result

Go solution

correspondant/original

package main

func shortestCompletingWord(licensePlate string, words []string) string {
    licenseCount := getCharCount(licensePlate)
    
    var result string
    for _, word := range words {
        if isCompletingWord(word, licenseCount) {
            if result == "" || len(word) < len(result) {
                result = word
            }
        }
    }
    return result
}

func getCharCount(s string) map[rune]int {
    count := make(map[rune]int)
    for _, c := range s {
        if isLetter(c) {
            count[toLower(c)]++
        }
    }
    return count
}

func isCompletingWord(word string, licenseCount map[rune]int) bool {
    wordCount := make(map[rune]int)
    for _, c := range word {
        wordCount[c]++
    }
    for char, cnt := range licenseCount {
        if wordCount[char] < cnt {
            return false
        }
    }
    return true
}

func isLetter(c rune) bool {
    return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')
}

func toLower(c rune) rune {
    if c >= 'A' && c <= 'Z' {
        return c + 'a' - 'A'
    }
    return c
}

Algorithm

Извлечь все буквы из licensePlate, игнорируя цифры и пробелы, и создать словарь для подсчета частоты каждой буквы.

Пройти по tableauу words, проверяя каждое слово на соответствие требованиям.

find самое короткое завершающее слово среди подходящих.

😎

Vacancies for this task

offres actives with overlapping task tags are affichés.

Toutes les offres

Il n'y a pas encore d'offres actives.