Shortest Completing Word

• Time:O(\Sigma |\texttt{words[i]}|)
• Space:O(26)

C++

``````class Solution {
public:
string shortestCompletingWord(string licensePlate, vector<string>& words) {
string ans(16, '.');
vector<int> 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<int>& c1, const vector<int> c2) {
for (int i = 0; i < 26; ++i)
if (c1[i] > c2[i])
return false;
return true;
}

vector<int> getCount(const string& word) {
vector<int> count(26);
for (const char c : word)
++count[c - 'a'];
return count;
}
};
``````

JAVA

``````class Solution {
public String shortestCompletingWord(String licensePlate, String[] words) {
String ans = "****************";
int[] count = new int[26];

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;
}
}
``````

Python

``````class Solution:
def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:
def isMatch(word: str) -> bool:
wordCount = Counter(word)
return False if any(wordCount[i] < count[i] for i in string.ascii_letters) else True

ans = '*' * 16
count = defaultdict(int)