Determine if a sentence is a pangram

Question

This definition is taken from Wikipedia:

A pangram (Greek: παν γράμμα, pan gramma, "every letter") or holoalphabetic sentence for a given alphabet is a sentence using every letter of the alphabet at least once. Pangrams have been used to display typefaces, test equipment, and develop skills in handwriting, calligraphy, and keyboarding.

I found a related code challenge here. It was in Python, so I tried to code this program in Java.

I took two steps:

1. Find if the String is a pangram
2. If a string is not a pangram, then find the missing letters

Please review the approach I have taken.

Pangram

import java.util.Set;
import java.util.TreeSet;

public class Pangram {
    private static final int ASCII_VALUE_OF_SMALL_CASE_CHAR_A = 97;
    private static final int ASCII_VALUE_OF_SMALL_CASE_CHAR_Z = 122;
    private Set<Character> distinctCharsInInputStringSortedAlphabetically = new TreeSet<Character>();

    public Pangram(final String inputString) {
        addUniqueAlphabetsToSet(inputString);
    }

    public boolean isPangram() {
        return distinctCharsInInputStringSortedAlphabetically.size() == 26;
    }

    private void addUniqueAlphabetsToSet(final String inputString) {
        for (Character character : inputString.toLowerCase().toCharArray()) {
            if ((int) character >= ASCII_VALUE_OF_SMALL_CASE_CHAR_A
                    && (int) character <= ASCII_VALUE_OF_SMALL_CASE_CHAR_Z) {
                distinctCharsInInputStringSortedAlphabetically.add(character);
            }
        }
    }

    public Set<Character> getMissingAlphabets() {
        Set<Character> missingAlphabets = new TreeSet<Character>();
        if (!isPangram()) {
            char alphabet_a = 'a';
            int asciiValue = (int) alphabet_a;
            for (Character alphabetsInInput : distinctCharsInInputStringSortedAlphabetically) {
                do {
                    if ((int) alphabetsInInput > asciiValue) {
                        missingAlphabets.add((char)asciiValue);
                    }
                    asciiValue++;
                } while ((int) alphabetsInInput >= asciiValue);

            }

            if(asciiValue <=ASCII_VALUE_OF_SMALL_CASE_CHAR_Z){
                do{
                    missingAlphabets.add((char)asciiValue);
                    asciiValue++;
                }while(asciiValue <=ASCII_VALUE_OF_SMALL_CASE_CHAR_Z);
            }

        }
        System.out.println("missingAlphabets" + missingAlphabets);
        return missingAlphabets;
    }

}

PangramTest

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;

import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;

import org.junit.Test;
public class PangramTest {

    @Test
    public void checkPangram_Test1(){
        Pangram pangram = new Pangram("The quick brown fox jumps over a lazy dog.");
        assertTrue(pangram.isPangram());
    }

    @Test
    public void checkPangram_Test2(){
        Pangram pangram = new Pangram("The quick red fox jumps over a lazy dog.");
        assertFalse(pangram.isPangram());
    }

    @Test
    public void checkPangram_WithReallyBigString(){
        Pangram pangram = new Pangram("Forsaking monastic tradition, twelve jovial friars gave up their vocation for a questionable existence on the flying trapeze");
        assertTrue(pangram.isPangram());
    }

    @Test
    public void checkPangram_Test3(){
        Pangram pangram = new Pangram("Crazy Fredericka bought many very exquisite opal jewels");
        assertTrue(pangram.isPangram());
    }

    @Test
    public void checkPangram_Test4(){
        Pangram pangram = new Pangram("Honest Fredericka bought many very exquisite opal jewels");
        assertFalse(pangram.isPangram());
    }

    @Test
    public void forPangramStringShouldReturnEmptySet(){
        Pangram pangram = new Pangram("The quick brown fox jumps over a lazy dog.");
        assertTrue(pangram.getMissingAlphabets().isEmpty());
    }

    @Test
    public void forNonPangramStringShouldReturnMissingAlphabets(){
        Pangram pangram = new Pangram("The quick brown fox jumps over busy dog.");
        Set<Character> actual = pangram.getMissingAlphabets();
        Set <Character>expected = new TreeSet<Character>();
        expected.add('a');
        expected.add('l');
        expected.add('z');

        assertEquals(expected,actual);
    }


    @Test
    public void forNonPangramStringShouldReturnMissingAlphabets_Test2(){
        Pangram pangram = new Pangram(" b cd x rs  ijk pno f vu");
        Set<Character> actual = pangram.getMissingAlphabets();
        Set <Character>expected = new HashSet<Character>();
        expected.add('a');
        expected.add('e');
        expected.add('g');
        expected.add('h');
        expected.add('l');
        expected.add('m');
        expected.add('q');
        expected.add('t');
        expected.add('w');
        expected.add('y');
        expected.add('z');

        assertEquals(expected,actual);
    }
}

Answer 1

The public interface of the class is nice and small. The code is laid out well and follows Java coding conventions. The tests have reasonable coverage.

There is a lot of unnecessary looping and casting in your code. Here's a more concise version that passes your tests:

public class Pangram {

    private final Set<Character> lettersRemaining = new HashSet<>();

    public Pangram(String s) {
        for (char ch = 'a'; ch <= 'z'; ch++) {
            lettersRemaining.add(ch);
        }
        s = s.toLowerCase();
        for (int i = 0; i < s.length(); i++) {
            lettersRemaining.remove(s.charAt(i));
        }
    }

    public boolean isPangram() {
        return lettersRemaining.isEmpty();
    }

    public Set<Character> getMissingAlphabets() {
        return new HashSet<>(lettersRemaining);
    }
}

Suggestions...

• Call it PangramCandidate rather than Pangram because it is misleading to have a non-pangram typed as a Pangram. As an analogy, you wouldn't expect String to have an isString() method.

• The very long variable name distinctCharsInInputStringSortedAlphabetically is referenced in several places which makes it tedious to read the code. I think you should find a briefer way of expressing what that variable represents.

• I do like your long test method names. However, the test method names starting with checkPangram_Test1..4 aren't very explanatory. Can you explain what exactly they are testing?

• The term MissingAlphabets seems awkward to me. I think you mean MissingLetters or MissingCharacters.

• In the tests, you can extract convenience methods for asserting whether a string is a pangram or not. This would reduce the amount of repetition in the test code.

  public static boolean isPangram(String s) {
      return new Pangram(s).isPangram();
  }
  
  public static void assertIsAPangram(String s) {
      assertTrue(isPangram(s));
  }
  
  public static void assertIsNotAPangram(String s) {
      assertFalse(isPangram(s));
  }
  

  I would actually suggest adding the isPangram(String s) convenience method to the PangramCandidate class because it will save callers time if that's all they need.

• Also, you might think about how to cater for foreign characters (e.g. é) or different alphabets, say Cyrillic or even Spanish. This checker works for English only.

• One of the lines in your test is very long due to a long String. I would suggest splitting it into two lines joined with +.

• If you use the Google Guava library you can create test sets more concisely, e.g.

  Sets.newHashSet('a', 'e', 'g', 'h', 'l', 'm', 'q', 't', 'w', 'y', 'z')
  

• In your code, the conditional:

  if ((int) character >= ASCII_VALUE_OF_SMALL_CASE_CHAR_A
          && (int) character <= ASCII_VALUE_OF_SMALL_CASE_CHAR_Z) {
  

  can be expressed more succinctly as:

  if (character >= 'a' && character <= 'z') {
  

  There is no need to cast to an int and there is little value in expressing these characters as constants. It's not like they are going to change, and 'a' is much quicker to read and comprehend than a wordy explanation.

Answer 2

A much simpler algorithm with a single pass would be using a set of the complete alphabet as the starting set, iterate over each letter in the input string, removing the letters from the set as you go. In the end, if the set is empty, the sentence is a pangram. If the set is not empty, the letters in it are the letters that were missed.

For extra efficiency, instead of a set, you could use a simple boolean array of length 'z' - 'a' + 1. Java initializes all elements to false by default. Then, for each letter c in the input string, set arr[c - 'a'] to true. In the end, if all elements are true, the sentence is a pangram. For the elements with index i that are false, the letter 'a' + i was missed.

Note that this is a better way of setting your constants:

private static final int ASCII_VALUE_OF_SMALL_CASE_CHAR_A = 'a';
private static final int ASCII_VALUE_OF_SMALL_CASE_CHAR_Z = 'z';

Here's alternative implementation using a boolean[] for storage:

class Pangram {

    private final Set<Character> missingLetters;

    public Pangram(String text) {
        boolean[] lettersUsed = new boolean['z' - 'a' + 1];
        for (char c : text.toLowerCase().toCharArray()) {
            if (c >= 'a' && c <= 'z') {
                lettersUsed[c - 'a'] = true;
            }
        }

        missingLetters = new HashSet<>();
        for (int i = 0; i < lettersUsed.length; ++i) {
            if (!lettersUsed[i]) {
                missingLetters.add((char) ('a' + i));
            }
        }
    }

    public boolean isPangram() {
        return missingLetters.isEmpty();
    }

    public Set<Character> getMissingAlphabets() {
        return missingLetters;
    }
}

I kept the same names so that it's usable with your unit tests, but since an alphabet is a set of letters, the name getMissingAlphabets is a bit off. getMissingLetters would be better.

Answer 3

Some test cases to be checked:

1. Null string (str = null).
2. Empty string (str = "").
3. Blank string (str = " ")
4. Instead of having multiple test case functions, have a dataProvider to pass multiple inputs to one testcase.

To find missing letters:

• Apache StringUtils.Difference(input_string, "abcdef...xyz")

• A small trick to convert uppercase to lowercase (OR the character with 32):

  • 'A'|32 = 'a'
  • 'a'|32 = 'a'