Title Description

Source: LeetCode

Give you a string licensePlate and a string array words. Please find and return the shortest complement word in words.

A complement is a word that contains all the letters in the licensePlate. Of all the complements, the shortest one is the shortest one.

When matching letters in the licensePlate:

Ignore numbers and spaces in {licensePlate.
Case insensitive.
If a letter appears more than once in the licensePlate, the number of occurrences of the letter in the complement should be the same or more.
For example: licensePlate = "aBc 12c", its complement should contain the letters' a ',' b '(ignoring uppercase) and two' c '. Possible complements are "abccdef", "caaacab" and "cbca".

Please find and return the shortest complement in words. The title data ensures that there must be a shortest complement. When more than one word meets the matching condition of the shortest complement word, take the first word in words.

Example 1:

Input: licensePlate = "1s3 PSt", words = ["step", "steps", "strip", "step"]
Output: "steps"
Explanation: the shortest complement should include "s", "p", "s" (ignoring case) and "t".
"step" contains "t", "p", but only one "s", so it does not meet the condition.
"steps" contains "t", "p" and two "s".
'stripe 'is missing an's'.
'step 'is missing an's'.
Therefore, "steps" is the only word that contains all letters, and it is also the answer to this example.

thinking

• filter

First, filter out the numbers and spaces in the given target string, and convert all uppercase letters to lowercase.

• Split statistic letter frequency

Then split words and strings and count the frequency of letters.

• Identify qualified words

Loop through the word array, determine the qualified words, and record the word length.

• Find the earliest and shortest word

Loop through the qualified word group, find the earliest and shortest word, and finally return the result.

python code

import re

class Solution(object):
    def shortestCompletingWord(self, licensePlate, words):
        """
        :type licensePlate: str
        :type words: List[str]
        :rtype: str
        """
        filter_num = re.sub(r'[0-9]' ,'' ,licensePlate)
        filter_space = re.sub(r' ' ,'' ,filter_num)
        result = {}
        target = self.letter_count(filter_space.lower())
        # Traversal words
        for word in words:
            if self.dict_is_meet(target,self.letter_count(word)):
                result.setdefault(word,len(word))

        # Print
        print(f'{str(result)}')

        # sort
        return self.dict_sorted(result)

    # sort
    def dict_sorted(self,dict):
        list = []
        for item in dict.items():
            if len(list) == 0:
                list.append(item)
            if item[1] < list[0][1]:
                list.clear()
                list.append(item)
        return list[0][0]

    # Judge whether the dictionary meets the conditions
    def dict_is_meet(self,dict1,dict2):
        for key in dict1.keys():
            if dict2.get(key) == None or dict1.get(key) != dict2.get(key):
                return 0
        return 1

    # Word split into letter count
    def letter_count(self,word):
        dict = {}
        # Letter cycle count
        for letter in word:
            if self.has_key(letter, dict):
                dict[letter] = dict.get(letter) + 1
            else:
                dict.setdefault(letter, 1)
        return dict

    # Determine whether the key is in the dictionary
    def has_key(self,key,dict):
        for k in dict.keys():
            if key == k:
                return 1
        return 0


if __name__ == '__main__':
    licensePlate = "1s3 456"
    words = ["looks","pest","stew","show"]

    s = Solution()
    result = s.shortestCompletingWord(licensePlate, words)
    print(result)
  

problem

When traversing the dictionary to find the last qualified word, the results of the method dict.items() running on the local and web pages are different, and the traversal order may be different, which should be noted.