Introduction

In this blog post, we will explore how to solve the LeetCode problem "748" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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.

Explanation

Here's a breakdown of the approach and the Python code:

• High-Level Approach:

  • Create a frequency map (dictionary) of the characters in the license plate (ignoring case and non-letters).
  • Iterate through the words, and for each word, check if it contains all the required characters with sufficient frequency.
  • Maintain the shortest completing word found so far.

• Complexity:

  • Runtime: O(N * M), where N is the number of words and M is the maximum length of a word. In the worst case, we might have to iterate through all words and count each word's characters to compare to the license plate's character counts.
  • Storage: O(1). The frequency maps for the license plate and each word will have a maximum size equal to the number of unique letters in the alphabet, which is constant.

Code

    def shortestCompletingWord(licensePlate: str, words: list[str]) -> str:
    """
    Finds the shortest completing word in words.

    Args:
        licensePlate: The license plate string.
        words: The list of words.

    Returns:
        The shortest completing word.
    """

    license_plate_freq = {}
    for char in licensePlate:
        if 'a' <= char <= 'z':
            char = char.lower()
            license_plate_freq[char] = license_plate_freq.get(char, 0) + 1
        elif 'A' <= char <= 'Z':
            char = char.lower()
            license_plate_freq[char] = license_plate_freq.get(char, 0) + 1

    shortest_word = None

    for word in words:
        word_freq = {}
        for char in word:
            word_freq[char] = word_freq.get(char, 0) + 1

        completing = True
        for char, freq in license_plate_freq.items():
            if char not in word_freq or word_freq[char] < freq:
                completing = False
                break

        if completing:
            if shortest_word is None or len(word) < len(shortest_word):
                shortest_word = word

    return shortest_word