Shortest Completing Word

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103]

    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:
        charProduct = self.getCharProduct(licensePlate.lower())
        shortest = "aaaaaaaaaaaaaaaaaaaa"  # 16 a's
        for word in words:
            if len(word) < len(shortest) and self.getCharProduct(word) % charProduct == 0:
                shortest = word
        return shortest

    def getCharProduct(self, plate: str) -> int:
        product = 1
        for c in plate:
            index = ord(c) - ord('a')
            if 0 <= index <= 25:
                product *= self.primes[index]
        return product

In this code, we maintain an array of prime numbers, primes. We have a method getCharProduct to get the product of prime numbers associated with each alphabetic character in a string.

The shortestCompletingWord method first converts the licensePlate to lowercase and gets its character product. Then it goes through each word in words and if a word’s length is shorter than the current shortest completing word’s length and the character product of the word is divisible by the character product of the licensePlate, we update the shortest completing word. Finally, the method returns the shortest completing word.

It’s important to note that this solution is based on the fundamental theorem of arithmetic, which states that every integer greater than 1 either is a prime number itself or can be represented as a product of prime numbers and that this representation is unique, up to the order of the factors. We’re using each prime number to uniquely represent a character from ‘a’ to ‘z’.

Identifying Problem Isomorphism

“Shortest Completing Word” can be approximately mapped to “Minimum Window Substring”.

Here’s the reasoning:

In “Shortest Completing Word”, you are given a string (licensePlate) and a list of words. The task is to find the shortest word in the list that contains all the characters in the licensePlate.

Similarly, in “Minimum Window Substring”, you are given two strings, s and t. The task is to find the minimum window in s which will contain all the characters in t.

Both problems involve finding a part of a string (or a complete string in the list, in the case of “Shortest Completing Word”) that contains all the characters from another string. They both require understanding of strings and may need similar approaches to solve, such as frequency counting of characters and sliding window techniques.

However, it’s not a direct isomorphism. “Minimum Window Substring” looks for a subsequence within a single string, while “Shortest Completing Word” looks for a sequence within a list of words.

“Shortest Completing Word” is simpler as it doesn’t require a sliding window technique. It mainly involves frequency count and string comparison. “Minimum Window Substring” is more complex as it requires the use of the sliding window technique to find the shortest substring within a larger string.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:
        licensePlate = ''.join([i.lower() for i in licensePlate if i.isalpha()])

        words = sorted(words, key=len)
        for word in words:
            for i in range(len(licensePlate)):
                if word.count(licensePlate[i]) < licensePlate.count(licensePlate[i]):
                    break
                if i == len(licensePlate)-1:
                    return word

Problem Classification

This problem belongs to the domain of String Processing and Character Counting in the wider area of Data Structures and Algorithms.

Identifying the ‘What’ components:

  1. Input: A string ’licensePlate’ and an array of strings ‘words’.
  2. Processing: Ignore numbers and spaces in ’licensePlate’, and treat letters as case insensitive.
  3. Condition: A word is considered a completing word if it contains all the letters in ’licensePlate’. If a letter appears more than once in ’licensePlate’, then it must appear in the word the same number of times or more.
  4. Output: The shortest completing word in ‘words’. If there are multiple shortest completing words, return the first one that occurs in ‘words’.

This is a Character Counting problem. We are required to count the frequency of each character in ’licensePlate’ and then compare it with the character count of each word in ‘words’. The problem involves the application of basic string operations, character frequency counting, and comparison of word lengths.

The task is to process the given string and list of words, apply the character counting technique to find the appropriate completing word based on the conditions provided, and then retrieve the shortest one from those.

Language Agnostic Coding Drills

  1. Identification of coding concepts:

    • Use of string methods: In Python, strings have several built-in methods. For instance, isalpha() is used to check if the character is a letter, lower() is used to convert a character to lowercase, and join() is used to join elements of an iterable into a string. These methods are applied to process the ’licensePlate’ string.
    • List comprehensions: List comprehensions are a unique way of creating lists in Python. Here, it is used to process the ’licensePlate’ string.
    • Sorting: The sorted() function is used to sort the words based on their length.
    • Loops: The code uses nested loops to iterate over the words and their individual characters.
    • Condition checking: The if statements are used to check certain conditions for the characters in the words.
    • Counting: The count() function is used to count the frequency of characters in a string.

  2. Ordered list of identified coding concepts:

    • Basic string methods and list comprehension (easy): These are fundamental concepts in Python. They are used here to process the ’licensePlate’ string and convert it into a format that can be compared with the words.
    • Use of loops (medium): While loops are a basic concept, nested loops can be more challenging to understand due to their complexity. Here, nested loops are used to iterate over the words and their individual characters.
    • Condition checking and counting (medium): These are more advanced concepts. Here, they are used to compare the frequency of characters in ’licensePlate’ and the words.
    • Sorting (hard): Sorting is a more advanced concept that is used here to sort the words based on their length. This makes it easier to find the shortest completing word.

  3. Problem-solving approach:

    • First, the ’licensePlate’ string is processed to extract only the letters and convert them to lowercase.
    • Then, the words are sorted in ascending order of their lengths.
    • The code then iterates over each word. For each word, it checks if it contains all the letters in ’licensePlate’ and if each letter in ’licensePlate’ appears in the word the same number of times or more. This is done by comparing the frequency of each letter in ’licensePlate’ and the word.
    • If a word meets the criteria, it is returned as the shortest completing word. If not, the code moves on to the next word. Since the words are sorted by length, the first word that meets the criteria is guaranteed to be the shortest.

Targeted Drills in Python

  1. Python-based coding drills for each identified concept:

    • Use of string methods and list comprehension:

      1
2
3

      string = "aBc 12c"
processed_string = ''.join([i.lower() for i in string if i.isalpha()])
print(processed_string)  # Outputs: "abc"

    • Use of loops:

      1
2
3
4

      words = ["apple", "banana", "cherry"]
for word in words:
    for char in word:
        print(char)  # Prints each character of each word on a new line

    • Condition checking and counting:

      1
2
3
4
5

      word = "abccdef"
license_plate = "abc"
for char in license_plate:
    if word.count(char) < license_plate.count(char):
        print(f"The character {char} does not occur enough times in the word.")

    • Sorting:

      1
2
3

      words = ["apple", "banana", "cherry"]
sorted_words = sorted(words, key=len)
print(sorted_words)  # Outputs: ['apple', 'cherry', 'banana']

  2. Problem-specific concept and its drill:

    The specific concept involved in this problem is finding the shortest completing word. It requires iterating over the words and checking if each character in the ’licensePlate’ appears in the word the same number of times or more.

    1
2
3
4
5
6
7
8

    words = ["abccdef", "caaacab", "cbca"]
license_plate = "abc"
for word in words:
    for i in range(len(license_plate)):
        if word.count(license_plate[i]) < license_plate.count(license_plate[i]):
            break
        if i == len(license_plate) - 1:
            print(word)  # Prints each completing word

    This drill is essential for solving the problem because it ensures that each letter in ’licensePlate’ appears in the word the same number of times or more. This is a key requirement for a word to be considered a completing word.

  3. Assembling the pieces to solve the problem:

    • Begin by processing the ’licensePlate’ string using the string methods and list comprehension drill. This will give us a string containing only the lowercase letters of ’licensePlate’.
    • Then, sort the words in ascending order of their lengths using the sorting drill. This ensures that we check the shortest words first.
    • Finally, iterate over the sorted words and check if each one is a completing word using the loops, condition checking and counting, and the problem-specific concept drills. The first word that meets the criteria is returned as the shortest completing word.