Problem overview
The function groupByFirstLetter takes a vector<string> named words of lowercase words and returns an unordered_map<string, vector<string>>. Each key is a first letter written as a one-character string, and its value is a vector of every word that starts with that letter. Inside a group the words keep the order they have in words. The order of the groups doesn't matter.
For ["apple", "banana", "avocado", "blueberry", "cherry"] the groups are a: [apple, avocado], b: [banana, blueberry] and c: [cherry]. A word that appears more than once in words appears that many times in its group.
Approach: a map from keys to lists
This is the grouping pattern. You walk through the input once, compute a key for each element, and append the element to the list stored under that key. Every word goes into exactly one group, so one pass is enough. Because the loop meets the words in their original order and appends each at the end of its group, every group keeps that order.
The nice part is that you never need to ask whether a group exists yet. The first time a letter appears, the map creates an empty vector for it, ready to receive the word.
Step by step
- Create
groups. An emptyunordered_map<string, vector<string>>: keys are one-letter strings, values are vectors of words. - Loop over the words. A range-based
forgives onestringnamedwordper turn. - Take the first letter.
word.substr(0, 1)is the substring that starts at position 0 and has length 1. It is astring, matching the map's key type. - Add the word to its group.
groups[first].push_back(word);appends it to the vector stored under that letter. - Return
groups.
The solution in C++
class Solution {
public:
unordered_map<string, vector<string>> groupByFirstLetter(vector<string> &words) {
unordered_map<string, vector<string>> groups;
for (string word : words) {
string first = word.substr(0, 1);
groups[first].push_back(word);
}
return groups;
}
};
The C++ details worth knowing:
[]creates the group. Whenfirstis not yet a key,groups[first]inserts it with a default-constructed value, which for a vector is an empty vector. It returns a reference to that vector, andpush_backthen adds the word to it. That is why noifis needed.substr(0, 1), notword[0].word[0]is achar, but the keys are strings. Achardoesn't convert to astringon its own.word.substr(0, 1)gives a one-characterstringdirectly.substron an empty string.substr(0, 1)on""returns an empty string rather than failing, butword[0]on an empty string would read past the text. The task promises every word has a letter.- Nested template brackets. The
>>at the end ofunordered_map<string, vector<string>>is fine in C++11 and later; older compilers wanted a space between the two. - Group order is unspecified. The order of words inside each vector is guaranteed, but the order in which the groups come out of the map is not.
Complexity
Time: O(n) on average for n words, since each map access takes constant time on average and push_back takes amortized constant time (copying a word costs time proportional to its length). Space: O(n), because every word is stored once in its group.
Edge cases and common mistakes
- One word.
["hello"]gives one group,h: [hello]. - Repeated words. Each occurrence is appended, so a word that appears twice appears twice in its group.
- Using
word[0]as the key. It is achar, which doesn't match thestringkey type and doesn't compile. - Order inside a group.
["dog", "cat", "deer", "cow", "duck"]puts "dog" before "deer" and "duck" in group "d", because that is the order they were met. - Replacing instead of appending. Assigning a one-word vector to
groups[first]would keep only the last word of each group.
Testing
Printed with the groups sorted by key:
["apple", "banana", "avocado", "blueberry", "cherry"]givesa: [apple, avocado],b: [banana, blueberry]andc: [cherry].
