HackerRank Regex Challenge: Detect HTML Tags

Question

Problem Statement

In this problem you will use regular expressions to help you detect the various Tags used in an HTML document.

Here are a few examples of tags:

The "p" tag for paragraphs:

<p>This is a paragraph</p>  

It is also okay to have one or more spaces before or after the tag name:

<  p >This is also a paragraph</p>

Then, there is also something called a void or an empty tag such as:

<p></p>

Some tags can also have attributes. For example, here we see the "a" tag which is used for adding links to a document.

[Google](http://www.google.com)

In the above case, "a" is the tag and "href" is an attribute, the value of which is http://www.google.com. Ignore any attributes. Your task is to find out all the tags present in the given document.

There are also tags such as this which haven't been split into an opening and closing tag (i.e, self-closing tags): '< p/>'

Input Format

The first line will contain N, the number of lines in the fragment. A valid HTML document or fragment.Leading and trailing spaces and indentation will be removed from the HTML lines.

Output Format

A list of all the tags present in the document, in lexicographical order, with semi-colons ";" between them. If a tag occurs multiple times, you just need to list it out once.

Sample Input

2
<p>[Example Link](http://www.quackit.com/html/tutorial/html_links.cfm)</p> <div> class="more-info">[More Link Examples...](http://www.quackit.com/html/examples/html_links_examples.cfm)</div>

Sample Output

a;div;p

I have used TreeSet to sort the tags lexicographically:

public class Detect_HTML_Tags {

    public static void main(String[] args) throws NumberFormatException, IOException {

        BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); 
        int N=Integer.parseInt(br.readLine().trim());
        String s="";

        for(int i=0;i<N;i++)
        {
            s+=br.readLine().trim();

        }
        TreeSet<String> tree=count_html_tags(s);
        int i=0;
        String s1="";
        for(String t:tree){
            s1=t;
            if(i==tree.size()-1)
                break;
            System.out.print(t+";");
            i++;
        }
        System.out.print(s1);
    }

    private static TreeSet<String> count_html_tags(String s) {
        String pat="\\s*(?:<([a-z][a-z0-9]*)|([\\[]))\\s*";
        Pattern p=Pattern.compile(pat);     
        Matcher m=p.matcher(s);
        TreeSet<String> set=new TreeSet<>();
        while(m.find())
        {
            String tag=m.group(0).trim();
            //System.out.println(tag);
            if(tag.equals("["))
                set.add("a");
            else
                set.add(m.group(1));            

        }
        return set;

    }
}

My code passes all the test cases. How can this solution be improved? Is the regex efficient enough or can it be improved further?

Answer 1

Naming/Style

public class Detect_HTML_Tags {

Usually classes get noun names, like HTML_Tag_Lister.

        int N = Integer.parseInt(br.readLine().trim());

It's more common in Java for all upper case variables to be constants:

        final int N = Integer.parseInt(br.readLine().trim());

Note that you can assign constants at runtime in Java.

        for(int i=0;i<N;i++)
        {

Most places you put the { on the same line as the command. Here you put it on the next line. While both are valid, it's generally easier to read the code if you pick one style or the other. There are some exceptional cases, but this isn't one of them.

        for (int i = 0; i < N; i++) {

As I went through your code, I added additional spaces for readability.

Favor interfaces over implementations

        TreeSet<String> tree=count_html_tags(s);

A TreeSet is a specific implementation. As a general rule, you want variable types to be interfaces. This allows you to switch the implementation without changing the variable type in multiple places. You could make the type a NavigableSet, but it should be sufficient to make it a SortedSet. It might even be enough to make it a Set or Collection with the current code. So something like

        SortedSet<String> tags = find_html_tags(s);

Note that you don't count the HTML tags. You find and return them.

Also, I find tags to be a more descriptive name than tree or set.

Later

    private static TreeSet<String> count_html_tags(String s) {

changes to

    private static SortedSet<String> count_html_tags(String s) {

Keep it simple if you can

In the following

        String s1="";
        for(String t:tree){
            s1=t;
            if(i==tree.size()-1)
                break;
            System.out.print(t+";");
            i++;
        }

You could change to

        if (tags.empty()) {
            return;
        }

        String last = tags.last();
        tags.remove(last);
        for (String tag : tags) {
            System.out.print(tag + ";");
        }
        System.out.println(last);

This avoids the i variable and updating the s1 variable on every iteration of the loop. You also don't have to check on every iteration of the loop in order to end it exactly one iteration early.

Note that last is a method on SortedSet. As best I can tell, this is the only reason why tags can't be a simple Collection in main.

Bugs?

The problem statement suggests that < p /> is a valid tag, but your regular expression won't match it because of the space between the < and the p.

The problem statement also suggests that <p> is only a valid tag if it has a matching </p>, but you never check for that. Perhaps that's not actually necessary. The problem statement says what is valid but doesn't mention you enforcing it.