Shortest Completing Word

🏠 ⬅️ ➡️

Given a string licensePlate and an array of strings words, find the shortest completing word in words.

A completing word is a word that contains all the letters in licensePlate. Ignore numbers and spaces in licensePlate, and treat letters as case insensitive. If a letter appears more than once in licensePlate, then it must appear in the word the same number of times or more.

For example, if licensePlate = "aBc 12c ", then it contains letters 'a', 'b' (ignoring case), and 'c' twice. Possible completing words are "abccdef ", "caaacab ", and "cbca ".

Return the shortest completing word in words. It is guaranteed an answer exists. If there are multiple shortest completing words, return the first one that occurs in words.

Example 1:

Input: licensePlate = "1s3 PSt ", words = [ "step ", "steps ", "stripe ", "stepple "] Output: "steps " Explanation: licensePlate contains letters 's', 'p', 's' (ignoring case), and 't'. "step " contains 't' and 'p', but only contains 1 's'. "steps " contains 't', 'p', and both 's' characters. "stripe " is missing an 's'. "stepple " is missing an 's'. Since "steps " is the only word containing all the letters, that is the answer.

Example 2:

Input: licensePlate = "1s3 456 ", words = [ "looks ", "pest ", "stew ", "show "] Output: "pest " Explanation: licensePlate only contains the letter 's'. All the words contain 's', but among these "pest ", "stew ", and "show " are shortest. The answer is "pest " because it is the word that appears earliest of the 3.

Constraints:

  • 1 <= licensePlate.length <= 7
  • licensePlate contains digits, letters (uppercase or lowercase), or space ' '.
  • 1 <= words.length <= 1000
  • 1 <= words[i].length <= 15
  • words[i] consists of lower case English letters.
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    character(len=7) :: licensePlate = "1s3 PSt "
    character(len=15), dimension(4) :: words = ["step ", "steps ", "stripe ", "stepple "]
    character(len=15) :: shortestCompletingWord

    shortestCompletingWord = solve(licensePlate, words)

    print *, shortestCompletingWord

contains

    function solve(licensePlate, words) result(shortestCompletingWord)
        implicit none
        character(len=*), intent(in) :: licensePlate
        character(len=*), intent(in) :: words(:)
        integer :: i, j, k, l, m
        logical :: found
        character(len=15) :: word
        character(len=15) :: temp
        integer, allocatable :: count(:)

        allocate(count(26))
        count = 0

        ! Ignore numbers and spaces in licensePlate
        do i = 1, len_trim(licensePlate)
            if (index('abcdefghijklmnopqrstuvwxyz', licensePlate(i:i)) /= 0) then
                k = index('abcdefghijklmnopqrstuvwxyz', licensePlate(i:i)) - 1
                count(k) = count(k) + 1
            end if
        end do

        ! Find the shortest completing word
        shortestCompletingWord = ""
        do i = 1, size(words)
            word = words(i)
            found = .true.
            do j = 1, len_trim(word)
                if (index('abcdefghijklmnopqrstuvwxyz', word(j:j)) /= 0) then
                    k = index('abcdefghijklmnopqrstuvwxyz', word(j:j)) - 1
                    if (count(k) < 1) then
                        found = .false.
                        exit
                    else
                        count(k) = count(k) - 1
                    end if
                end if
            end do
            if (found) then
                if (len_trim(shortestCompletingWord) == 0) then
                    shortestCompletingWord = word
                else
                    temp = word
                    call sort(temp)
                    call sort(shortestCompletingWord)
                    if (temp < shortestCompletingWord) then
                        shortestCompletingWord = word
                    end if
                end if
            end if
        end do

        deallocate(count)

    end function solve

    subroutine sort(string)
        implicit none
        character(len=*), intent(inout) :: string
        integer :: i, j
        character :: temp

        do i = 1, len_trim(string) - 1
            do j = i + 1, len_trim(string)
                if (string(i:i) > string(j:j)) then
                    temp = string(i:i)
                    string(i:i) = string(j:j)
                    string(j:j) = temp
                end if
            end do
        end do

    end subroutine sort

end program main
✅ Compiled
❌ Executed
❌ Correct 
! Declare variables
integer :: i, j, k, l, m, n, o
character(len=7) :: licensePlate
character(len=15) :: words(1000)
character(len=15) :: shortestWord
logical :: found

! Initialize variables
shortestWord = ""
found = .false.

! Read input
read(*,*) licensePlate
read(*,*) words

! Loop through words
do i = 1, 1000
    ! Check if word contains all letters in licensePlate
    found = .true.
    do j = 1, 7
        if (index(licensePlate, words(i)(j:j)) == 0) then
            found = .false.
            exit
        end if
    end do
    
    ! If word is completing, check if it is shortest
    if (found) then
        if (shortestWord == "") then
            shortestWord = words(i)
        else
            ! Check length of shortestWord and current word
            if (len(shortestWord) > len(words(i))) then
                shortestWord = words(i)
            end if
        end if
    end if
end do

! Print output
write(*,*) shortestWord

end
🌐 Data from online sources 
def shortestCompletingWord(licensePlate: str, words: list[str]) -> str:
    from collections import Counter

    lp_count = Counter(c.lower() for c in licensePlate if c.isalpha())

    result = ""
    for word in words:
        word_count = Counter(word)

        valid = all(word_count[ch] >= count for ch, count in lp_count.items())

        if valid and (not result or len(word) < len(result)):
            result = word

    return result

1. Create a hash map (or dictionary in Python) to store the count of characters in the `licensePlate`.
  1. Iterate through the words array.
  2. For each word, create a hash map storing the count of characters in the current word.
  3. Check whether the current word is a valid completing word by comparing the counts in both hash maps. It's valid if it has equal or more count of characters compared to the licensePlate for each character.
  4. If the word is valid and the result is empty or the length of the word is shorter than the result's length, update the result with the current word.
  5. Return the result.
🌐 Data from online sources 
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>

std::string shortestCompletingWord(std::string licensePlate, std::vector<std::string>& words) {
    std::unordered_map<char, int> lp_count;
    for (char c : licensePlate)
        if (isalpha(c))
            lp_count[tolower(c)]++;

    std::string result = "";
    for (const std::string& word : words) {
        std::unordered_map<char, int> word_count;
        for (char c : word)
            word_count[c]++;

        bool valid = true;
        for (const auto& [ch, count] : lp_count)
            if (word_count[ch] < count) {
                valid = false;
                break;
            }

        if (valid && (result.empty() || word.length() < result.length()))
            result = word;
    }
    return result;
}

1. Create a hash map (or dictionary in Python) to store the count of characters in the `licensePlate`.
  1. Iterate through the words array.
  2. For each word, create a hash map storing the count of characters in the current word.
  3. Check whether the current word is a valid completing word by comparing the counts in both hash maps. It's valid if it has equal or more count of characters compared to the licensePlate for each character.
  4. If the word is valid and the result is empty or the length of the word is shorter than the result's length, update the result with the current word.
  5. Return the result.