Leetcode – Shortest Completing Word Solution in Python

Spread the love

In this article, we will be focusing on the problem titled “Shortest Completing Word” (Leetcode Problem 748), outlining a Python-based solution.

Problem Statement

The problem is described as follows:

Find the minimum length word from a given dictionary words, which has all the letters from the string licensePlate. Such a word is said to complete the given string licensePlate.

Here, for letters we ignore case. For example, “P” on the licensePlate still matches “p” on the word. It is guaranteed an answer exists. If there are multiple answers, return the one that occurs first in the array.

The license plate might have the same letter occurring multiple times. For example, given a licensePlate of “PP”, the word “pair” does not complete the “PP”, but the word “supper” does.

Note:

  • Each word in words list will be in lower case; the licensePlate will be lowercase and upper case.
  • The same word in the words list may be chosen multiple times.

For instance, given licensePlate = “1s3 P”, and words = [“step”, “steps”, “stripe”, “stepple”], return “steps” because it contains all the letters in “s” and “p” (ignoring the case) that occur in licensePlate.

Approach to Solve the Problem

The problem can be broken down into two tasks:

  1. Extract all the letters from the licensePlate.
  2. Find the shortest word from words that contains all these letters.

To extract the letters from the licensePlate, we can iterate over each character and add it to our collection if it is a letter.

To find the shortest completing word, we can iterate over each word in words and check if it contains all the letters from licensePlate. If it does and it is shorter than the current shortest completing word, we update our answer.

Below is the Python solution following the described approach:

class Solution:
    def shortestCompletingWord(self, licensePlate, words):
        """
        :type licensePlate: str
        :type words: List[str]
        :rtype: str
        """
        licensePlate = [ch.lower() for ch in licensePlate if ch.isalpha()]
        words.sort(key=len) # Sort words by length
        
        for word in words:
            if all(word.count(ch) >= licensePlate.count(ch) for ch in set(licensePlate)):
                return word

In this code, we first extract all the letters from the licensePlate and convert them to lowercase. We then sort the words by their length. For each word, we check if the count of each character in licensePlate is less than or equal to its count in the word. If a word satisfies this condition, it is a completing word and, since words is sorted by length, it is the shortest completing word.

Time and Space Complexity

The time complexity of the solution is O(nmlog(m) + nmk), where n is the length of words, m is the average length of a word in words, and k is the length of licensePlate. This is because we are sorting the words and for each word, we are counting the occurrence of each character in licensePlate.

The space complexity is O(n), which is the space required to store licensePlate and words.

Testing the Solution

Let’s test our solution with the example case from Leetcode:

s = Solution()
print(s.shortestCompletingWord("1s3 P", ["step", "steps", "stripe", "stepple"]))  # Expected output: "steps"

As we can see, the output is correct.

Conclusion

The “Shortest Completing Word” problem is a relatively simple problem that requires knowledge of basic string and list operations in Python. By breaking the problem down into manageable tasks, we can easily solve it using a straightforward approach.

Leave a Reply