10
\$\begingroup\$

Problem:

You are given a randoms string containing only lowercase letters and you need to find if the string contains ALL the vowels.

Input:

First line contains N , the size of the string. Second line contains the letters (only lowercase).

Output:

Print "YES" (without the quotes) if all vowels are found in the string, "NO" (without the quotes) otherwise.

Constraints:

The size of the string will not be greater than 10,000 1 ≤ N ≤ 10000

The above problem is from hackerearth.com and below is my attempt to solve this problem and I need your review on my codestyle, and efficiency and need your help to make it better.

public class TestClass {

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

    BufferedReader input = new BufferedReader(new InputStreamReader(System.in));

    System.out.println("Enter the Length of the String");
    final int inputLength = Integer.parseInt(input.readLine());//the size of the string

    if (inputLength >= 10000) {
        System.err.println("The size of the string can not be greater than 10,000");
        System.exit(1);
    }

    System.out.println("Enter letters");
    String word = input.readLine().toLowerCase().trim();

    //remove all white space
    word = word.replaceAll(" ", "");

    final char[] vowels = {'a', 'e', 'i', 'o', 'u'};
    short found = 0;

    for (final char c : vowels) if (searchForVowel(c, word)) found++;

    String result = (found == vowels.length) ? "yes" : "no";

    System.out.println(result);
}

private static boolean searchForVowel(char vowel, String word) {
    final char[] chars = word.toCharArray();
    boolean isContains = false;

    for (char c : chars) {
        if (c == vowel) {
            isContains = true;
            break;
        }
    }

    return isContains;
  }

}
\$\endgroup\$
4
  • 1
    \$\begingroup\$ As for efficiency, although it doesn´t change much, you could iterate over the input just one time to check if it contains all vowels instead of one time for each vowel. At least in c++ chars are just integers to their ascii value, so if java is the same you can use an array of 26 and count the repetitions of each character, and if its a vowel check if it has found all \$\endgroup\$
    – juvian
    Dec 2, 2015 at 13:27
  • 1
    \$\begingroup\$ @juvian You either only need an array of 5 or you'd need an array of 65k. \$\endgroup\$
    – Voo
    Dec 2, 2015 at 17:47
  • \$\begingroup\$ @Voo yeah, guessed it was just a-z letters but 5 is enough \$\endgroup\$
    – juvian
    Dec 2, 2015 at 18:50
  • \$\begingroup\$ You're not including all your vowels. You've omitted Y (as in Joy) and W (as in Cow). \$\endgroup\$
    – corsiKa
    Dec 3, 2015 at 11:13

7 Answers 7

16
\$\begingroup\$

I would like to make one remark concerning the performance of your solution: you need to check if the word contains all vowels ('a', 'e', 'i', 'o' and 'u'), which means the following:

  • If the word does not contain 'a', then it's not good, else:
  • If the word does not contain 'e' (we already know it contains 'a'), it's not good, else:
  • ...

But: in the English language, some vowels are more popular than others. Imagine following percentages (not real ones):
60% of the English words contain an 'a'
80% of the English words contain an 'e'
40% of the English words contain an 'i'
20% of the English words contain an 'o'
10% of the English words contain an 'u'

If you start searching with 'a', then with 'e', then with 'i', 'o', and 'u', you have following situation:
40% probability that you have found out that the word is not good, then:
20% probability that you have found out that the word is not good, then:
60% probability that you have found out that the word is not good, then:
80% probability that you have found out that the word is not good, then:
90% probability that you have found out that the word is not good.

=> in other words, you'll spend a lot of time investigating letters which are not popular.

However, if you re-order your search criteria:

  • first search for 'u'
  • then search for 'o'
  • then search for 'i'
  • then search for 'a'
  • and only finally search for 'e'

=> like this, you will find much sooner the words without 'u' (90% of the words), or the ones without an 'o' (80% of the words), ..., and this might heavily improve the performance of your search.

I must add that the percentages I have written down are just examples (for the correct percentages you need to search on frequency analysis of the English language).

Good luck

\$\endgroup\$
6
  • 2
    \$\begingroup\$ Welcome to Code Review, good observation and easy to overlook! \$\endgroup\$ Dec 2, 2015 at 15:46
  • \$\begingroup\$ There's nothing suggesting that an input string is semanticly well formed English. How do we know that Ü is not a possible vowel? In a real world application, it's possible to perform data analysis to tune performance, but the suggested optimization goes further down the problematic path that begins with hard coding the vowels into the program. \$\endgroup\$ Dec 2, 2015 at 19:24
  • \$\begingroup\$ you'd also need an early exit condition (typically else break; is sufficient here) \$\endgroup\$
    – njzk2
    Dec 2, 2015 at 23:15
  • 1
    \$\begingroup\$ @benrudgers Normally I'd agree with you, but given the source of the problem and it's nature as an intellectual exercise rather than a real-world issue, assuming aeiou is probably safe. These kinds of problem also tend to get "graded" on performance, which is unfortunate. \$\endgroup\$
    – Eric Stein
    Dec 3, 2015 at 1:15
  • \$\begingroup\$ For longish strings (a few hundred KBs on vaguely recent machines) traversing the string from start once for each vowel is going to be much worse than checking if each character is a vowel (thus traversing the string only once) due to how the cache works. If your string doesn't fit the L2 cache you don't want to have it evicted at each iteration when looking for the next vowel; instead, just go forward once and play along with the prefetching machinery (which may even put the next bytes in L1 while you are checking the previous ones). \$\endgroup\$ Dec 3, 2015 at 9:05
8
\$\begingroup\$

Implementation

You only need to go through the array one time. Keep track of whether or not you've found each vowel, then return based on the results. You can return early if you find all five, and you can not check if the current character is not a vowel.

Trimming the whitespace is probably costing you more than just walking through the characters and ignoring them. That makes it a performance hit for unnecessary code clutter.

Trinary statements are best used when you need the result to chain into something else. In your case, an if () {} else {} would be cleaner to read.

You don't actually need to check the size of the String they're passing in to you. I don't read it as a requirement for you to error if the number is too big, but rather an invariant on the input size. Since your method doesn't care about the input size, it shouldn't error arbitrarily.

You also don't need to prompt for them to provide letters. I'm sure that they just push the two lines.

You should always close streams. Use try-with-resources.

A Scanner might be a better choice than an input stream for ease of use.

With all these modifications, your code might look more like:

import java.io.IOException;
import java.util.Scanner;

public final class TestClass {

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

        try (final Scanner scanner = new Scanner(System.in)) {
            scanner.nextLine();
            final String word = scanner.nextLine();
            if (hasAllVowels(word)) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
    }

    private static boolean hasAllVowels(final String input) {
        boolean hasA = false;
        boolean hasE = false;
        boolean hasI = false;
        boolean hasO = false;
        boolean hasU = false;

        for (int i = 0; i < input.length(); i++) {
            switch (input.charAt(i)) {
            case 'a':
                hasA = true;
                break;
            case 'e':
                hasE = true;
                break;
            case 'i':
                hasI = true;
                break;
            case 'o':
                hasO = true;
                break;
            case 'u':
                hasU = true;
                break;
            default:
                continue;
            }

            if (hasA && hasE && hasI && hasO && hasU) {
                return true;
            }
        }
        return false;
    }

}
\$\endgroup\$
5
  • \$\begingroup\$ +1 for keeping track of the presence of each vowel separately so you can exit as soon as possible. \$\endgroup\$ Dec 2, 2015 at 20:02
  • \$\begingroup\$ Are we sure we want to dump toCharArray here? Seems like we could switch(input.charAt(i) which is both clearer and faster (considering it is likely to get JIT'd out). Also a big +1 for Scanner, I don't know why more people don't use it for things like this. \$\endgroup\$
    – corsiKa
    Dec 3, 2015 at 11:15
  • \$\begingroup\$ You should only close resources you own. You do not own System.in so you shouldn't close it. \$\endgroup\$
    – Johnbot
    Dec 3, 2015 at 13:27
  • \$\begingroup\$ @corsiKa You are correct about input.charAt(i). I'll update the code. \$\endgroup\$
    – Eric Stein
    Dec 3, 2015 at 14:07
  • \$\begingroup\$ @Johnbot In principle, I agree. In practice, System.in is open for the entire running of a toy application. It's an annoying corner case caused by chaining close() statements. \$\endgroup\$
    – Eric Stein
    Dec 3, 2015 at 14:15
6
\$\begingroup\$

Meets Requirements?

  1. The instructions refer to "the first line". This strongly suggests that the program should read from a file rather than the console. Doing so would get rid of the hard coded prompt strings.

  2. The program output is "yes" or "no". The requirement is "YES" or "NO".

Architecture

Even better would be decoupling the "business logic" of determining whether the contents of the string contain all the vowels from input and output. Modularizing the code into 1) getting input, 2) inspecting the input, 3) packaging the output provides an opportunity for code reuse in situations where the programmer's understanding of requirements may change (as may be the case here).

Design

I'm not a fan of performance optimization that isn't backed by measurements showing there is an actual problem. My suspicion is that searching the string once for each vowel is almost certainly reasonable in this case even if processing the list one letter at a time is likely to allow better worst case performance in theory since the list would only need to be traversed once.

On the other hand, removing white space from the input string is not consistent with the requirements and is potential source of bugs in code that has to be maintained and adapted to the changing world.

Validation

  1. Since the specification states N is between 0 and 10,001 exclusive. Either there's no reason to test the length of input is less than 10,0001 or it should be tested against the lower bound as well as the upper.

  2. bufferedreader does not specify a character encoding. The default may be fine, but since the requirements are underspecified (vowels in what language?, a string in what language?) make the programmer's assumptions explicit is worth the effort. This is a case where it might even be appropriate to comment the code to document the conundrum.

\$\endgroup\$
4
\$\begingroup\$

You ask for the length of the input, and then ask for the input. That is okay (from my knowledge) if you're using arrays, but you're using a much higher level language here. You should ask for an input and then check the length of it. Otherwise what stops me from entering 1 as length and a 20000 long string?

System.out.println("Enter letters");
String word = input.readLine().toLowerCase().trim();
final int inputLength = word.length();

if (inputLength >= 10000) {
    System.err.println("The size of the string can not be greater than 10,000");
    System.exit(1);
}

This way, everything is safe!

I don't think you should remove whitespaces, it's a costly operation that serves no purposes. After all, what's the difference between a whitespace and the letter "n" in your context? None! You care about the vowels, nothing else. With replaceAll you'll go through your whole string once to remove white spaces. This isn't useful in your case.

At the moment, your algorithm goes this way : For each vowel, check the whole string if I'm contained. This is an \$O(mn)\$ where \$m\$ is the number of vowels and \$n\$ is the length of the word.

I think we should do it this way : Go through the whole string and check if each character is a vowel. This is an \$O(n)\$ operation, where \$n\$ is the length of word.

The goal of these optimization is to go through the string only once, which would be faster.

It would look like this :

for (final char c : word) if (characterIsAVowel(c)) found++;

Now, how do we deal with characterIsAVowel? Simple! We'll use an HashSet. The HashSet is a data structure that is very performant to check if an item is contained in the set, what we call an \$O(1)\$ operation. See where this is going?

We'll create a set that contains each vowel.

HashSet<Character> vowels = new HashSet<Character>();
vowels.add('a');
vowels.add('e');
vowels.add('i');
vowels.add('o');
vowels.add('u');

So, what does it look like now?

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

    BufferedReader input = new BufferedReader(new InputStreamReader(System.in));

    String word = "aeiuzzz";
    final int inputLength = word.length();

    if (inputLength >= 10000) {
        System.err.println("The size of the string can not be greater than 10,000");
        System.exit(1);
    }

    HashSet<Character> vowels = initializeVowels();
    short found = 0;

    for (final char c : word.toCharArray()) {
        //remove returns true if the value was removed! So it's found only once
        if (vowels.remove(c)) {
            found++;
        }
    }        

    String result = (found == vowels.size()) ? "yes" : "no";

    System.out.println(result);
}

private static HashSet<Character> initializeVowels() {
    HashSet<Character> vowels = new HashSet<Character>();
    vowels.add('a');
    vowels.add('e');
    vowels.add('i');
    vowels.add('o');
    vowels.add('u');

    return vowels;
}

In theory, this algorithm is more efficient and extensible. Though, considering that vowels is very small (5 elements), there probably wouldn't be a big difference. Still, it's good to see how it should be done. Though, consider vowels don't change very often, using a solution like @Eric's one will probably be faster.

Notice that I added the brackets to your for and if. It is preferred because forgetting a bracket can be expansive!

\$\endgroup\$
7
  • \$\begingroup\$ You get a false positive and a false negative because you're only counting total vowels, not discrete vowels. Perhaps you forgot vowels.remove(c)? You might also want to return early if the set is empty. \$\endgroup\$
    – Eric Stein
    Dec 2, 2015 at 16:08
  • \$\begingroup\$ Also, when I made the modifications from my above comment, the original solution is an order of magnitude faster than the HashSet solution. :( That's a test of 5 million iterations over inputs of length 1-100. \$\endgroup\$
    – Eric Stein
    Dec 2, 2015 at 16:29
  • \$\begingroup\$ @EricStein You're right about the first comment there's something missing :p And yeah, I can see why your solution is faster. Mine is easier to extend, but I doubt we'll add vowels any time soon :p \$\endgroup\$
    – IEatBagels
    Dec 2, 2015 at 16:48
  • 1
    \$\begingroup\$ I think you can get more bang for your buck with if (vowels.remove(c)) { found++; } You currently find the vowel twice - once to check if it's there, once to remove it. May as well just try to remove it. I think your performance hits are tied to hashCode() and all the implicit char <--> Character casting, but I haven't done real analysis - just a guess. \$\endgroup\$
    – Eric Stein
    Dec 2, 2015 at 16:54
  • 1
    \$\begingroup\$ I think that found == vowels.size() should be replaced by vowels.isEmpty() (and then you don't even need the found variable!) \$\endgroup\$
    – oliverpool
    Dec 2, 2015 at 22:17
4
\$\begingroup\$
if (inputLength >= 10000) {
    System.err.println("The size of the string can not be greater than 10,000"

Take care when reading the requirements. The restriction on N, the length of the string, is 1 ≤ N ≤ 10000, but this not what you have coded. Your condition above allows N to be 0 (which is an invalid value) and does not allow it to be 10000 (which is a valid value). The error message is correct, but does not correspond to the condition.

\$\endgroup\$
2
\$\begingroup\$

Your coding style is good! great going! But try not complicate yourself. The code you have written is complex! Though it serves the purpose of your problem, you must write codes such that others will have no trouble in understanding your code. Instead of all those, try using built in classes in java which make your work easy! Use something like this, and iterate over your vowel array!

string.indexOf('a')

Let me just show a code sample!

String vowels=new String("aeiou");
for(int i=0;i<vowels.length();i++)
{
    if(word.indexOf(vowels.charAt(i)) == -1)
    {
         System.out.println("String doesn't contain all vowels");
         System.exit(0);
    }
}
System.out.println("String contains all vowels");

The above code should be quite clear and it should do the task. The string.indexOf(char) returns a -1 if there is no match. Else it returns the index of match. Hope it's clear! Cheers!

\$\endgroup\$
1
  • \$\begingroup\$ Hello! You're saying the code is complex but you don't really explain much about it. I think you should explain a little bit more your answer if you want it to be useful :) \$\endgroup\$
    – IEatBagels
    Dec 2, 2015 at 14:22
1
\$\begingroup\$

Your algorithm does 5 passes over the input string with several instructions per character. If you instead just iterate over input string once and keep track of what characters occur in the string (assuming ASCII here) then you can check if all vowels occurred easily, and without any branches.

boolean lut[] = new boolean[256];
for(char c : input.toCharArray()){
    lut[c] = true;
}

boolean hasAllVowels = lut['a'] && lut['i'] && lut['u'] && lut['e'] && lut['0'];

The formulation of the problem:

"only contains lowercase letters"

is telling you that you won't get any non-latin letters so the ASCII assumption should hold here. If you can't assume ASCII then use a bigger table or a HashSet<Character>.

As for other aspects of the code, those have already been covered by others.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.