# 748. Shortest Completing Word

• Time: $O(\Sigma |\texttt{words[i]}|)$
• Space: $O(26)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 class Solution { public: string shortestCompletingWord(string licensePlate, vector& words) { string ans(16, '.'); vector count(26); for (const char c : licensePlate) if (isalpha(c)) ++count[tolower(c) - 'a']; for (const string& word : words) if (word.length() < ans.length() && isComplete(count, getCount(word))) ans = word; return ans; } private: // Check if c1 is a subset of c2 bool isComplete(const vector& c1, const vector c2) { for (int i = 0; i < 26; ++i) if (c1[i] > c2[i]) return false; return true; } vector getCount(const string& word) { vector count(26); for (const char c : word) ++count[c - 'a']; return count; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class Solution { public String shortestCompletingWord(String licensePlate, String[] words) { String ans = "****************"; int[] count = new int[26]; for (char c : licensePlate.toCharArray()) if (Character.isLetter(c)) ++count[Character.toLowerCase(c) - 'a']; for (final String word : words) if (word.length() < ans.length() && isComplete(count, getCount(word))) ans = word; return ans; } // Check if c1 is a subset of c2 private boolean isComplete(int[] c1, int[] c2) { for (int i = 0; i < 26; ++i) if (c1[i] > c2[i]) return false; return true; } private int[] getCount(final String word) { int[] count = new int[26]; for (final char c : word.toCharArray()) ++count[c - 'a']; return count; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution: def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str: def isMatch(word: str) -> bool: wordCount = collections.Counter(word) return False if any(wordCount[i] < count[i] for i in string.ascii_letters) else True ans = '*' * 16 count = collections.defaultdict(int) for c in licensePlate: if c.isalpha(): count[c.lower()] += 1 for word in words: if len(word) < len(ans) and isMatch(word): ans = word return ans