Leetcode 1002: Find Common Characters
Given a list of words, return an array of characters that appear in all words. The output should include duplicates of characters as they appear in each word, and the answer can be returned in any order.
Problem
Approach
Steps
Complexity
Input: The input is a list of words where each word is a string of lowercase English letters.
Example: words = ['apple', 'grape', 'maple']
Constraints:
• 1 <= words.length <= 100
• 1 <= words[i].length <= 100
• words[i] consists of lowercase English letters
Output: The output is an array of characters that appear in all words of the list. The characters should appear as many times as they appear in each word, and can be in any order.
Example: ['p', 'e', 'l']
Constraints:
• The output array will only contain lowercase English letters.
Goal: The goal is to identify the characters that appear in all words, taking into account their frequency in each word.
Steps:
• Create a frequency array to track the minimum number of occurrences of each character across all words.
• Iterate through each word, updating the frequency array to reflect the minimum occurrences of each character.
• Generate the result by adding characters to the output list according to their minimum frequency.
Goal: Ensure that the solution works efficiently for the input size.
Steps:
• The algorithm should handle up to 100 words with lengths up to 100 characters.
Assumptions:
• The input list contains valid words with lowercase English letters only.
• Input: Input: words = ['hello', 'cello', 'mellow']
• Explanation: The common characters between all words are 'e', 'l', and 'l', which appear at least once in each word.
• Input: Input: words = ['blue', 'clue', 'glue']
• Explanation: The common characters are 'l', 'u', and 'e', appearing at least once in each word.
Approach: The problem can be solved by using frequency counts for each character in every word and comparing them to find the minimum occurrences for each character across all words.
Observations:
• We need to track the occurrences of each character in every word and update the result accordingly.
• This problem can be tackled by using a frequency array and iterating over the words to find common characters.
Steps:
• Initialize a frequency array to store the minimum occurrences of each character.
• For each word, create a count array to track the frequency of characters in that word.
• Update the global frequency array by comparing each character's frequency in the current word.
• After processing all words, generate the result by including each character the number of times it appears in the frequency array.
Empty Inputs:
• If the input is an empty list, return an empty result array.
Large Inputs:
• The solution should efficiently handle the maximum input size with up to 100 words and 100 characters per word.
Special Values:
• If there are no common characters between the words, return an empty result.
Constraints:
• The solution should avoid unnecessary complexity and optimize for large inputs.
vector<string> commonChars(vector<string>& words) {
vector<int> frq(26, INT_MAX);
for(string& s: words) {
vector<int> cnt(26, 0);
for(char x: s) cnt[x - 'a']++;
for(int i = 0; i < 26; i++)
frq[i] = min(frq[i], cnt[i]);
}
vector<string> res;
for(int i = 0; i < 26; i++)
for(int j = 0; j < frq[i]; j++)
res.push_back(string(1, 'a' + i));
return res;
}
1 : Function Definition
vector<string> commonChars(vector<string>& words) {
Defines the function `commonChars` which takes a vector of strings and returns a vector of strings containing the common characters among them.
2 : Frequency Initialization
vector<int> frq(26, INT_MAX);
Initializes a frequency vector `frq` of size 26, where each element represents the maximum possible count of each character ('a' to 'z'). The frequency is set to `INT_MAX` to ensure that the first comparison will set the correct minimum frequency.
3 : Loop Over Words
for(string& s: words) {
Iterates over each word in the input list `words`.
4 : Count Frequency in Word
vector<int> cnt(26, 0);
For each word, a `cnt` vector is initialized to count the occurrences of each character in the word.
5 : Character Counting
for(char x: s) cnt[x - 'a']++;
Iterates over each character in the current word and updates the corresponding count in the `cnt` vector based on the character's position in the alphabet.
6 : Frequency Update
for(int i = 0; i < 26; i++)
Loops through all 26 characters of the alphabet.
7 : Min Frequency Update
frq[i] = min(frq[i], cnt[i]);
For each character, updates the frequency vector `frq` by taking the minimum count of the character between the current word and the previous words.
8 : Result Initialization
vector<string> res;
Initializes an empty vector `res` to store the result, which will be the common characters.
9 : Loop Over Characters
for(int i = 0; i < 26; i++)
Iterates over each character (from 'a' to 'z').
10 : Add Common Characters
for(int j = 0; j < frq[i]; j++)
For each character, adds the character to the result vector `res` based on its minimum frequency (how many times it appears in all the words).
11 : Push Character to Result
res.push_back(string(1, 'a' + i));
Creates a string from the character (using its ASCII value) and adds it to the result vector `res`.
12 : Result Return
return res;
Returns the vector `res`, which contains all the common characters.
Best Case: O(n * m)
Average Case: O(n * m)
Worst Case: O(n * m)
Description: The time complexity is O(n * m), where n is the number of words and m is the maximum length of a word, since we process each character in each word.
Best Case: O(26)
Worst Case: O(26)
Description: The space complexity is O(26) for the frequency arrays used to track the minimum counts of characters, as there are only 26 possible lowercase English letters.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus