FastPrep
Problem · Graph

Group Transitive String Aliases

Learn this problem
● MediumApple logoAppleFULLTIMEPHONE SCREEN

Problem statement

You are given an array pairs, where each row contains two string aliases. Alias relationships are bidirectional and transitive: if a is an alias of b, and b is an alias of c, then all three strings belong to the same alias group.

Return every connected alias group. Within each group, sort all words lexicographically; the first word is therefore the key that the source associates with that group. Return the groups in lexicographic order by their first words.

Function

groupAliases(pairs: String[][]) → List<List<String>>

Examples

Example 1

pairs = [["a","b"],["b","c"],["d","e"]]return = [["a","b","c"],["d","e"]]

The first two pairs connect a, b, and c. The third pair forms the separate group [d,e].

Example 2

pairs = [["z","x"],["m","m"],["x","y"],["z","x"]]return = [["m"],["x","y","z"]]

A self-pair keeps m as a one-word group. Repeated pairs do not change connectivity.

Constraints

  • 1 <= pairs.length <= 10^5
  • pairs[i].length == 2
  • Every alias is a non-empty printable-ASCII string of length at most 30.
  • Duplicate pairs and self-pairs are allowed.

More Apple problems

drafts saved locally
public List<List<String>> groupAliases(String[][] pairs) {
    // Write your code here
}
pairs[["a","b"],["b","c"],["d","e"]]
expected[["a","b","c"],["d","e"]]
checking account