Check if string has all the letters of the alphabet

Question

What would be the best logic to check all the letters in a given string.

If all the 26 letters are available in the provided string, I want to check that and perform so ops. eg. Pack my box with five dozen liquor jugs.

1. Would using a Hash be useful?
2. Or using a bit map? or any other way?

BTW my code would be in Java.

Answer 1

I'd go for a bitmap. If you increment a counter each time you set an entry in the bitmap to 1, you can early return as soon as you've seen all the letters. I hope this is not for enforcing password requirements.

Answer 2

Keep an boolean array of size 26. Each position of the array says whether a particular character is present or not (a is at 0, b is at 1, etc.). Initially all are set to false. Now do a single scan through the string character by character, setting the value for that character to true. At the end, check if all 26 indexes contain true.

Answer 3

An array of 26 booleans is enough, each entry representing on of the alphabet letters. You can set the entry to true when the letter is found.

Answer 4

I'd go for a sieve algorithm on the 26 letters. Just my $.02.

Edit: An array of 26 values that represent the 26 letters of the alphabet. Then scan the string, checking each letter as you encounter it. At the end, check if the 26 letters have been checked.

Answer 5

Using a BitMap, I'm assuming you meant case insenstive.

Update: Solution by Thomas is more efficient, than the following. :) Use that one.

    //
    String test  = "abcdefeghjiklmnopqrstuvwxyz";

    BitSet alpha = new BitSet(26);
    for(char ch : test.toUpperCase().toCharArray())
        if(Character.isLetter(ch))
            alpha.set(ch - 65);

    System.out.println(alpha.cardinality() == 26);

Answer 6

Not yet fully optimized:

public static void main(String... a) {
    String s = "Pack my box with five dozen liquor jugs.";
    int i=0;
    for(char c : s.toCharArray()) {
        int x = Character.toUpperCase(c);
        if (x >= 'A' && x <= 'Z') {
            i |= 1 << (x - 'A');
        }
    }
    if (i == (i | ((1 << (1 + 'Z' - 'A')) - 1))) {
        System.out.println("ok");
    }
}

Answer 7

You could iterate over your string for each letter of the alphabet you want to check. When you find the letter you are looking for, continue with the next. If you don’t, abort. Here is some pseudo-code:

found = true;
for (letter in letters) {
    if (!string.contains(letter)) {
        found = false;
        break;
    }
}

This way you do not need to store the information for each letter but you have to search the string again and again for each letter. What you end up using will depend on your requirements: should it be fast? Should it use little memory? Your decision. :)