Group error messages that differ only in numbers
A re-solve is due. Start from a blank template and solve it without the editorial. That is what makes the pattern stick.
The problem
Error messages often differ only in the numbers inside them: timeout after 30 ms on shard 4 and timeout after 31 ms on shard 9 are the same problem.
Group the messages whose text is identical once every run of digits is treated as the same. Return the groups as lists of positions in messages. Order the positions inside a group from first to last, and the groups by the position of their first message.
- 0 ≤ messages.length ≤ 200,000
- each message is at most 200 characters
Examples
groupErrors(["timeout after 30 ms", "disk full", "timeout after 4 ms", "disk full"])returns[[0, 2], [1, 3]]groupErrors(["shard 1 down", "shard 12 down", "shard down"])returns[[0, 1], [2]]A message with no number is a different shape.groupErrors([])returns[]
Hints
Hint 1 of 2
Turn each message into a key that is the same for messages that should be grouped: replace every run of digits with one placeholder.
Hint 2 of 2
Keep a Map from key to the list of positions. A Map keeps keys in the order they were first added, which is the order the groups need.
Editorial
Opens once you solve the problem, or after three checked attempts.
Read the editorial and a reference solution
Grouping is a hash map whose key is the shape the items share. Here the shape is the message with every run of digits replaced by one placeholder, so after 30 ms and after 4 ms both become after # ms.
The regular expression matters: \d+ replaces a whole number at once, while \d replaces each digit, so numbers of different lengths give different keys.
Use a Map. A plain object already has keys such as constructor and __proto__, so a message with that text finds something that is not its group. A Map also iterates in insertion order, which is exactly the order of each group's first message.
function groupErrors(messages) {
const groups = new Map();
messages.forEach((m, i) => {
const key = m.replace(/\d+/g, '#');
if (!groups.has(key)) groups.set(key, []);
groups.get(key).push(i);
});
return [...groups.values()];
}Complexity. O(total length of the messages) time and space.
Your solution
TypeScript types are removed before the tests run, not checked: the tests judge what the code does.
Tab indents. Press Esc, then Tab, to leave the editor. Ctrl+Enter runs the examples.