Day 28: HackerRank 30 Days Of Code Solution | RegEx, Patterns, and Intro to Databases

Day 28 of HackerRank's 30 Days of Code mixes two topics: regular expressions and a pretend database table. The task is to filter rows by email domain and print names in sorted order, which is basically SELECT name FROM emails WHERE email LIKE '%@gmail.com' ORDER BY name written in Java.

The coding is short. What is worth learning is how to write a pattern that matches exactly what you mean, and the difference between find() and matches() in Java's regex API. Both come up constantly in real work, from form validation to log parsing.

Problem

Imagine a table called Emails with two columns: a first name and an email ID. You get N rows of this table. Print the first names of everyone whose email ends with @gmail.com, sorted alphabetically, one per line. Names can repeat, and each matching row is printed.

Input format: the first line has N. Each of the next N lines has a first name and an email ID separated by a space.

Output format: the matching first names in alphabetical order, each on a new line.

Constraints: 2 <= N <= 30. First names use only lowercase letters a to z and are at most 20 characters. Email IDs use only lowercase letters, @ and ., and are at most 50 characters.

Input
6
riya riya@gmail.com
julia julia@julia.me
julia sjulia@gmail.com
julia julia@gmail.com
samantha samantha@gmail.com
tanya tanya@gmail.com

Output
julia
julia
riya
samantha
tanya

One of the three julias uses julia.me, so only two julias appear in the output.

Approach

Break it into three small steps.

1. Write the pattern. A valid gmail ID here is one or more allowed characters, then @gmail.com, and nothing after. In regex: [a-z.]+@gmail\.com. The [a-z.] is a character class (inside square brackets the dot is literal), + means "one or more", and \. is an escaped dot. In a Java string literal the backslash itself must be escaped, so it becomes "[a-z.]+@gmail\\.com".
2. Check each row. Compile the pattern once with Pattern.compile, outside the loop, and call matcher(email).matches() for each email. matches() succeeds only if the entire string fits the pattern, so we do not need ^ and $ anchors.
3. Sort and print. Collect matching names in a list, call Collections.sort, and print them.

Dry run: riya matches. julia@julia.me does not, because the text after @ is not gmail.com. sjulia@gmail.com and julia@gmail.com match, so "julia" is added twice. samantha and tanya match. The list is [riya, julia, julia, samantha, tanya], which sorts to julia, julia, riya, samantha, tanya.

Solution in Java

The previous solution here used .+@gmail\\.com$ with find(). That works for this input, but .+ accepts any character, including another @, and find() searches for a match anywhere, so it depends on the $ anchor to stay correct. It also created a raw ArrayList, which gives an unchecked warning. The version below is stricter and cleaner.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
import java.util.regex.Pattern;

public class Solution {

    // One or more allowed characters, then exactly "@gmail.com" at the end.
    // The dot is escaped because a bare "." in regex means "any character".
    private static final Pattern GMAIL = Pattern.compile("[a-z.]+@gmail\\.com");

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<String> names = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            String firstName = sc.next();
            String email = sc.next();
            // matches() checks the WHOLE string, so no ^ or $ is needed
            if (GMAIL.matcher(email).matches()) {
                names.add(firstName);
            }
        }

        Collections.sort(names);           // alphabetical, duplicates kept
        for (String name : names) {
            System.out.println(name);
        }
    }
}

Extra tests I ran: zoe@gmailxcom is rejected (this is why the dot must be escaped; an unescaped . would accept the "x"), amit@gmail.com.in is rejected because something follows ".com", and bob@mail.gmail.com is rejected because the domain after @ is "mail.gmail.com", not "gmail.com". With no gmail users at all, the program prints nothing, which is the correct output.

Output

julia
julia
riya
samantha
tanya

Complexity

Time: O(N x L) to check the emails, where L is the email length (at most 50), plus O(N log N) to sort the names. With N at most 30, this is instant.

Space: O(N) for the list of names.

Common mistakes

• Not escaping the dot. @gmail.com as a regex matches "@gmailXcom" too, because . means any character.
• Using contains("@gmail.com"). It also accepts "x@gmail.com.fake.org". endsWith("@gmail.com") is a valid non-regex alternative for this problem.
• Mixing up find() and matches(). find() looks for the pattern anywhere in the text. matches() requires the whole string to match. Pick the one that fits, or use anchors with find().
• Using a Set for names. That removes duplicates, but the expected output lists julia twice.

Related: Java Regex builds an IP address pattern, and Java Regex 2 - Duplicate uses backreferences.

Tip: try to solve the problem yourself before reading the solution. Use the code as a reference to check your approach, and make sure you understand why it works.

More HackerRank solutions All coding problems MCQ practice