748. Shortest Completing Word LeetCode Solution

Last updated: February 19, 2025

In this guide, you will get 748. Shortest Completing Word LeetCode Solution with the best time and space complexity. The solution to Shortest Completing Word problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Shortest Completing Word solution in C++
Shortest Completing Word solution in Java
Shortest Completing Word solution in Python
Additional Resources

748. Shortest Completing Word LeetCode Solution image

Problem Statement of Shortest Completing Word

Given a string licensePlate and an array of strings words, find the shortest completing word in words.
A completing word is a word that contains all the letters in licensePlate. Ignore numbers and spaces in licensePlate, and treat letters as case insensitive. If a letter appears more than once in licensePlate, then it must appear in the word the same number of times or more.
For example, if licensePlate = “aBc 12c”, then it contains letters ‘a’, ‘b’ (ignoring case), and ‘c’ twice. Possible completing words are “abccdef”, “caaacab”, and “cbca”.
Return the shortest completing word in words. It is guaranteed an answer exists. If there are multiple shortest completing words, return the first one that occurs in words.

Example 1:

Input: licensePlate = “1s3 PSt”, words = [“step”,”steps”,”stripe”,”stepple”]
Output: “steps”
Explanation: licensePlate contains letters ‘s’, ‘p’, ‘s’ (ignoring case), and ‘t’.
“step” contains ‘t’ and ‘p’, but only contains 1 ‘s’.
“steps” contains ‘t’, ‘p’, and both ‘s’ characters.
“stripe” is missing an ‘s’.
“stepple” is missing an ‘s’.
Since “steps” is the only word containing all the letters, that is the answer.

Example 2:

Input: licensePlate = “1s3 456”, words = [“looks”,”pest”,”stew”,”show”]
Output: “pest”
Explanation: licensePlate only contains the letter ‘s’. All the words contain ‘s’, but among these “pest”, “stew”, and “show” are shortest. The answer is “pest” because it is the word that appears earliest of the 3.

Constraints:

1 <= licensePlate.length <= 7
licensePlate contains digits, letters (uppercase or lowercase), or space ' '.
1 <= words.length <= 1000
1 <= words[i].length <= 15
words[i] consists of lower case English letters.

Complexity Analysis

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

748. Shortest Completing Word LeetCode Solution in 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:
  // Returns true 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;
  }
};
/* code provided by PROGIEZ */

748. Shortest Completing Word LeetCode Solution in Java

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

  // Returns true 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;
  }
}
// code provided by PROGIEZ

748. Shortest Completing Word LeetCode Solution in Python

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
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents