LC 748

String HashTable
HashTable
Publish Date:   2022-01-22

Solution to LeetCode 748 Shortest Completing Word.

LeetCode 748

Shortest Completing Word (Easy). [link]

Note that the letter on the license plate can be uppercase or lowercase while words contain only lowercase letters. If there are multiple matches, return the shortest one (the max length of word in ‘words’ list is 1000).

Time complexity O(N + L + M * 26), where N is the length of licensePlace, L is the total lengths of words, and M is the length of ‘words’ list. Space complexity O(26).

class Solution(object):
    def shortestCompletingWord(self, licensePlate, words):
        """
        :type licensePlate: str
        :type words: List[str]
        :rtype: str
        """
        hash = {chr(i + ord('a')): 0 for i in range(26)} # create a HashTable
        for char in licensePlate:
            if char.isalpha():
                hash[char.lower()] += 1 # count each character
        MIN = 1001 # need it to pick the shortest
        ans = '' 
        for w in words:
            if not self.isMatch(hash, w): # if not satisfy
                continue
            if len(w) >= MIN: # if not the shortest
                continue
            MIN = len(w) # record the word length
            ans = w # record the answer
        return ans
    
    def isMatch(self, hash, w):
        newHash = {chr(i + ord('a')): 0 for i in range(26)} # create a new HashTable for a word
        for char in w:
            newHash[char] += 1 # count each character 
        for i, j in zip(hash, newHash):
            if newHash[j] < hash[i]: 
                return False
        return True

Use Python API Counter.

class Solution(object):
    def shortestCompletingWord(self, licensePlate, words):
        """
        :type licensePlate: str
        :type words: List[str]
        :rtype: str
        """
        cnt = Counter(ch.lower() for ch in licensePlate if ch.isalpha())
        # if cnt - Counter(word) is empty, this word satisfies the condition
        # if there are multiple matches, find the shortest
        return min((word for word in words if not cnt - Counter(word)), key=len)
String HashTable
  TOC