LeetCode 748: Shortest Completing Word (Letter-Frequency Coverage Check)
LeetCode 748StringCountingToday we solve LeetCode 748 - Shortest Completing Word.
Source: https://leetcode.com/problems/shortest-completing-word/
English
Problem Summary
Given a string licensePlate and a list of words, find the shortest word that contains all letters in licensePlate (case-insensitive), including repeated letters. Digits and spaces are ignored.
Key Insight
Convert licensePlate into a 26-length required frequency array. For each candidate word, count letters and check whether every required frequency is met. The first shortest valid word is the answer.
Algorithm
- Build array need[26] from letters in licensePlate.
- Initialize answer as empty.
- For each word, build have[26] and verify have[i] >= need[i] for all letters.
- If valid and shorter than current answer, update answer.
- Return answer after scanning all words.
Complexity Analysis
Let n be number of words and m be average word length.
Time: O(n * (m + 26)) = O(nm).
Space: O(26) auxiliary (excluding input).
Common Pitfalls
- Forgetting to count repeated letters (e.g., need two ps).
- Treating digits as required characters.
- Returning earliest valid word without enforcing shortest length.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public String shortestCompletingWord(String licensePlate, String[] words) {
int[] need = countLetters(licensePlate);
String ans = "";
for (String w : words) {
if (covers(need, countLetters(w)) && (ans.isEmpty() || w.length() < ans.length())) {
ans = w;
}
}
return ans;
}
private int[] countLetters(String s) {
int[] cnt = new int[26];
for (char ch : s.toCharArray()) {
if (Character.isLetter(ch)) {
cnt[Character.toLowerCase(ch) - 'a']++;
}
}
return cnt;
}
private boolean covers(int[] need, int[] have) {
for (int i = 0; i < 26; i++) {
if (have[i] < need[i]) return false;
}
return true;
}
}func shortestCompletingWord(licensePlate string, words []string) string {
need := countLetters(licensePlate)
ans := ""
for _, w := range words {
have := countLetters(w)
if covers(need, have) && (ans == "" || len(w) < len(ans)) {
ans = w
}
}
return ans
}
func countLetters(s string) [26]int {
var cnt [26]int
for _, ch := range s {
if ch >= 'A' && ch <= 'Z' {
ch = ch - 'A' + 'a'
}
if ch >= 'a' && ch <= 'z' {
cnt[ch-'a']++
}
}
return cnt
}
func covers(need, have [26]int) bool {
for i := 0; i < 26; i++ {
if have[i] < need[i] {
return false
}
}
return true
}class Solution {
public:
string shortestCompletingWord(string licensePlate, vector<string>& words) {
array<int, 26> need = countLetters(licensePlate);
string ans;
for (const string& w : words) {
auto have = countLetters(w);
if (covers(need, have) && (ans.empty() || w.size() < ans.size())) {
ans = w;
}
}
return ans;
}
private:
array<int, 26> countLetters(const string& s) {
array<int, 26> cnt{};
for (char ch : s) {
if (isalpha(static_cast<unsigned char>(ch))) {
cnt[tolower(static_cast<unsigned char>(ch)) - 'a']++;
}
}
return cnt;
}
bool covers(const array<int, 26>& need, const array<int, 26>& have) {
for (int i = 0; i < 26; i++) {
if (have[i] < need[i]) return false;
}
return true;
}
};class Solution:
def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:
def count_letters(s: str) -> List[int]:
cnt = [0] * 26
for ch in s.lower():
if 'a' <= ch <= 'z':
cnt[ord(ch) - ord('a')] += 1
return cnt
need = count_letters(licensePlate)
ans = ""
def covers(need: List[int], have: List[int]) -> bool:
for i in range(26):
if have[i] < need[i]:
return False
return True
for w in words:
have = count_letters(w)
if covers(need, have) and (not ans or len(w) < len(ans)):
ans = w
return ansvar shortestCompletingWord = function(licensePlate, words) {
const countLetters = (s) => {
const cnt = new Array(26).fill(0);
for (const chRaw of s) {
const ch = chRaw.toLowerCase();
if (ch >= 'a' && ch <= 'z') cnt[ch.charCodeAt(0) - 97]++;
}
return cnt;
};
const covers = (need, have) => {
for (let i = 0; i < 26; i++) {
if (have[i] < need[i]) return false;
}
return true;
};
const need = countLetters(licensePlate);
let ans = "";
for (const w of words) {
const have = countLetters(w);
if (covers(need, have) && (ans === "" || w.length < ans.length)) {
ans = w;
}
}
return ans;
};中文
题目概述
给定字符串 licensePlate 和单词数组 words，找出最短的“完整单词”：它必须包含 licensePlate 中所有字母（忽略大小写、数字和空格），并且重复字母次数也要满足。
核心思路
先把车牌中的字母统计成 need[26]。遍历每个候选单词，统计为 have[26]，检查每个字母是否满足 have[i] >= need[i]。满足则参与最短长度比较。
算法步骤
- 统计车牌必需字母频次数组 need。
- 初始化答案为空字符串。
- 逐个处理 words：统计频次并进行覆盖性校验。
- 若覆盖成功且长度更短，更新答案。
- 遍历结束返回答案。
复杂度分析
设单词数量为 n，平均长度为 m。
时间复杂度：O(n * (m + 26))，可记为 O(nm)。
空间复杂度：O(26)（不计输入存储）。
常见陷阱
- 忽略重复字母需求（例如需要两个 p）。
- 把数字或空格也当成匹配目标。
- 找到第一个可行词就返回，忘记比较“最短”。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public String shortestCompletingWord(String licensePlate, String[] words) {
int[] need = countLetters(licensePlate);
String ans = "";
for (String w : words) {
if (covers(need, countLetters(w)) && (ans.isEmpty() || w.length() < ans.length())) {
ans = w;
}
}
return ans;
}
private int[] countLetters(String s) {
int[] cnt = new int[26];
for (char ch : s.toCharArray()) {
if (Character.isLetter(ch)) {
cnt[Character.toLowerCase(ch) - 'a']++;
}
}
return cnt;
}
private boolean covers(int[] need, int[] have) {
for (int i = 0; i < 26; i++) {
if (have[i] < need[i]) return false;
}
return true;
}
}func shortestCompletingWord(licensePlate string, words []string) string {
need := countLetters(licensePlate)
ans := ""
for _, w := range words {
have := countLetters(w)
if covers(need, have) && (ans == "" || len(w) < len(ans)) {
ans = w
}
}
return ans
}
func countLetters(s string) [26]int {
var cnt [26]int
for _, ch := range s {
if ch >= 'A' && ch <= 'Z' {
ch = ch - 'A' + 'a'
}
if ch >= 'a' && ch <= 'z' {
cnt[ch-'a']++
}
}
return cnt
}
func covers(need, have [26]int) bool {
for i := 0; i < 26; i++ {
if have[i] < need[i] {
return false
}
}
return true
}class Solution {
public:
string shortestCompletingWord(string licensePlate, vector<string>& words) {
array<int, 26> need = countLetters(licensePlate);
string ans;
for (const string& w : words) {
auto have = countLetters(w);
if (covers(need, have) && (ans.empty() || w.size() < ans.size())) {
ans = w;
}
}
return ans;
}
private:
array<int, 26> countLetters(const string& s) {
array<int, 26> cnt{};
for (char ch : s) {
if (isalpha(static_cast<unsigned char>(ch))) {
cnt[tolower(static_cast<unsigned char>(ch)) - 'a']++;
}
}
return cnt;
}
bool covers(const array<int, 26>& need, const array<int, 26>& have) {
for (int i = 0; i < 26; i++) {
if (have[i] < need[i]) return false;
}
return true;
}
};class Solution:
def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:
def count_letters(s: str) -> List[int]:
cnt = [0] * 26
for ch in s.lower():
if 'a' <= ch <= 'z':
cnt[ord(ch) - ord('a')] += 1
return cnt
need = count_letters(licensePlate)
ans = ""
def covers(need: List[int], have: List[int]) -> bool:
for i in range(26):
if have[i] < need[i]:
return False
return True
for w in words:
have = count_letters(w)
if covers(need, have) and (not ans or len(w) < len(ans)):
ans = w
return ansvar shortestCompletingWord = function(licensePlate, words) {
const countLetters = (s) => {
const cnt = new Array(26).fill(0);
for (const chRaw of s) {
const ch = chRaw.toLowerCase();
if (ch >= 'a' && ch <= 'z') cnt[ch.charCodeAt(0) - 97]++;
}
return cnt;
};
const covers = (need, have) => {
for (let i = 0; i < 26; i++) {
if (have[i] < need[i]) return false;
}
return true;
};
const need = countLetters(licensePlate);
let ans = "";
for (const w of words) {
const have = countLetters(w);
if (covers(need, have) && (ans === "" || w.length < ans.length)) {
ans = w;
}
}
return ans;
};
Comments