#3839

Number of Prefix Connected Groups

medium · 60.5% accepted · 45 likes · top 59%

array · hash table · string · counting

Description

You are given an array of strings words and an integer k.

Two words a and b at distinct indices are prefix-connected if a[0..k-1] == b[0..k-1].

A connected group is a set of words such that each pair of words is prefix-connected.

Return the number of connected groups that contain at least two words, formed from the given words.

Note:

- Words with length less than k cannot join any group and are ignored.

- Duplicate strings are treated as separate words.

Solution