class Solution1(object):
def shortestCompletingWord(self, licensePlate, words):
"""
use words to cover licensePlate
use word array to calc count
"""
import gc
licensePlate = list(map(lambda x:x.lower(),list(filter(lambda x: x.isalpha(), list(licensePlate)))))
lowcase = [0 for i in range(26)]
count = 0
result = None
for char in licensePlate:
lowcase[ord(char) - 97] +=1
count += 1
for word in words:
tmp_lowcase = lowcase[:]
tmp_count = count
for char in word:
if tmp_lowcase[ord(char) - 97] > 0:
tmp_lowcase[ord(char) - 97] -=1
tmp_count -= 1
if tmp_count ==0:
if result == None or len(result) > len(word):
result = word
continue
del tmp_lowcase
del tmp_count
return result
class Solution2(object):
"""
use dictionary , change word to dict and see if the word's dict has enough count for each char
"""
def shortestCompletingWord(self, licensePlate, words):
licensePlate = list(map(lambda x: x.lower(), list(filter(lambda x: x.isalpha(), list(licensePlate)))))
result = None
for word in words:
if self.helper(licensePlate, word) :
if result is None or len(result) > len(word):
result = word
return result
def helper(self, licensePlate, word):
dict = {}
for char in word:
dict[char] = dict.get(char, 0) +1
for char in licensePlate:
if dict.get(char, 0) == 0:
return False
dict[char] -=1
return True
class Solution3(object):
"""
use 26 prime to take place of the 26 lowercase letters
so if the product of word could exact division licensePlate it mean the word contains the licensePlate
"""
def shortestCompletingWord(self, licensePlate, words):
from functools import reduce
from operator import mul
prime = [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]
licensePlate = list(map(lambda x: x.lower(), list(filter(lambda x: x.isalpha(), list(licensePlate)))))
licensePlate = reduce(mul, map(lambda x: prime[ord(x)-97], licensePlate))
result = None
for word in words:
word_numer = reduce(mul, map(lambda x: prime[ord(x) -97], list(word)))
if word_numer % licensePlate ==0:
if result is None or len(result) > len(word):
result = word
return result
class Solution4(object):
"""
use Counter and intersection operation of Counter
"""
def shortestCompletingWord(self, licensePlate, words):
from collections import Counter
lc_counter = Counter(filter(lambda x: x.isalpha(), licensePlate.lower()))
return min([w for w in words if Counter(w) & lc_counter == lc_counter], key=len)
