README_EN.md

748. Shortest Completing Word

中文文档

Description

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.

Solutions

Python3

class Solution:
    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:
        def count(word):
            counter = [0] * 26
            for c in word:
                counter[ord(c) - ord('a')] += 1
            return counter

        def check(counter1, counter2):
            for i in range(26):
                if counter1[i] > counter2[i]:
                    return False
            return True

        counter = count(c.lower() for c in licensePlate if c.isalpha())
        ans, n = None, 16
        for word in words:
            if n <= len(word):
                continue
            t = count(word)
            if check(counter, t):
                n = len(word)
                ans = word
        return ans

Java

class Solution {
    public String shortestCompletingWord(String licensePlate, String[] words) {
        int[] counter = count(licensePlate.toLowerCase());
        String ans = null;
        int n = 16;
        for (String word : words) {
            if (n <= word.length()) {
                continue;
            }
            int[] t = count(word);
            if (check(counter, t)) {
                n = word.length();
                ans = word;
            }
        }
        return ans;
    }

    private int[] count(String word) {
        int[] counter = new int[26];
        for (char c : word.toCharArray()) {
            if (Character.isLetter(c)) {
                ++counter[c - 'a'];
            }
        }
        return counter;
    }

    private boolean check(int[] counter1, int[] counter2) {
        for (int i = 0; i < 26; ++i) {
            if (counter1[i] > counter2[i]) {
                return false;
            }
        }
        return true;
    }
}

C++

class Solution {
public:
    string shortestCompletingWord(string licensePlate, vector<string>& words) {
        vector<int> counter = count(licensePlate);
        int n = 16;
        string ans;
        for (auto& word : words) {
            if (n <= word.size()) continue;
            vector<int> t = count(word);
            if (check(counter, t)) {
                n = word.size();
                ans = word;
            }
        }
        return ans;
    }

    vector<int> count(string& word) {
        vector<int> counter(26);
        for (char& c : word)
            if (isalpha(c))
                ++counter[tolower(c) - 'a'];
        return counter;
    }

    bool check(vector<int>& counter1, vector<int>& counter2) {
        for (int i = 0; i < 26; ++i)
            if (counter1[i] > counter2[i])
                return false;
        return true;
    }
};

Go

func shortestCompletingWord(licensePlate string, words []string) string {
	count := func(word string) []int {
		counter := make([]int, 26)
		for _, c := range word {
			if unicode.IsLetter(c) {
				counter[c-'a']++
			}
		}
		return counter
	}

	check := func(cnt1, cnt2 []int) bool {
		for i := 0; i < 26; i++ {
			if cnt1[i] > cnt2[i] {
				return false
			}
		}
		return true
	}

	counter := count(strings.ToLower(licensePlate))
	var ans string
	n := 16
	for _, word := range words {
		if n <= len(word) {
			continue
		}
		t := count(word)
		if check(counter, t) {
			n = len(word)
			ans = word
		}
	}
	return ans
}

...