Check if string has all the letters of the alphabet

java algorithm logic

19,808

Solution 1

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");
    }
}

Solution 2

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);

Solution 3

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.

Solution 4

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.

Solution 5

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.

View more solutions

19,808

Author by

Vivek

I am trying to learn and put my grey cells to work

Updated on June 05, 2022

Comments

Vivek almost 2 years
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.
Thomas Mueller over 13 years

So... use "int" instead of a BitSet. It has enough bits. In Java, "int" will always have 32 bits, unlike in C.
st0le over 13 years

Wouldn't using 0x3FFFFFF be faster?
Andrew Simpson over 13 years

The right side of the | contains no variables, so it would be calculated at compile time and stored as a constant. (This assumes a compiler with an optimizer.)
st0le over 13 years

@Blrfl, I meant faster compilation. heehee... :) true!
Thomas Mueller over 13 years

Actually, no need for (i | ...), you might as well use if (i == (1 << (1 + 'Z' - 'A')) - 1) - or Integer.bitCount(i) == 26.
Thomas Mueller over 13 years

You can get rid of the if (x >= 'A' && x <= 'Z') - but then you need to keep the (i | ...) as it is now.
Filburt over 13 years

OP requirements would allow you to break if one character is missing so you wouldn't need to check the indexes in the end.
Chris Knight over 13 years

Yes, but this is much more readable and maintainable. And besides, mabye this operation doesn't need to be efficient.
MAK over 13 years

@Filburt: I don't understand what you mean. My check at the end is something like this boolean ret=true;for(int i=0;i<26 && ret;i++) ret&=seen[i];return ret;.
Chris over 13 years

You don't need to do a second scan, just increment a counter when you turn on a bit, i.e. ...{ count+=(!letters[i]); letters[i]++} ... return 26 == count;
MAK over 13 years

@CodeninjaTim: That's right :). Thanks for pointing that out.
Filburt over 13 years

@MAK Well if you discover that there's no "b" in your input string it's a) pointless to try 24 more characters and b) pointless to scan your array at the end. In that case you would want your function return false immediately.
Pete Kirkham over 13 years

Will grow the bit set for characters which aren't ASCII Latin.
Rachel over 10 years

Can you elaborate, bit operation that you are doing in details to provide some context?
Thomas Mueller over 10 years

Details: set each bit in the (32-bit-) integer where the given character is in the text. Bit 0 = A, bit 1 = B,... Then check if all bits that represent A - Z are set. If you don't understand bit operations then you need to read about it.
Thomas Mueller over 7 years

This answer is incorrect. For example the following test string will incorrectly report "false": abcdefeghjiklmnopqrstuvwxyzäöü, and the following will incorrectly report "true": abcdefeghjiklmnopqrstuvwäöü. Please note there are 47444 (!) distinct "uppercase" characters for the Unicode codepoints 0 .. 0xffff.
Mathews Sunny over 6 years

Please add an Explanation