Wednesday, November 7, 2012

Simple code for finding missing alphabet letters in a sentence

I consider no code is trash even if it's too trivial. And I also hate the sensation of knowing I code something similar before, but have to repeat the coding because I didn't save it. Some time ago I had to code a solution for a simple problem as part of the recruiting process in a company. The problem to solve is to find the missing letters of the alphabet in a given sentence.


import java.util.HashSet;
import java.util.Set;
 
/**
* Test code to find missing letters of the alphabet from a String sentence.
* @author gabriel.solano
*
*/
public class MissingLetters {
 
private final int ASCII_CODE_FOR_LETTER_A = 97;
private final int ASCII_CODE_FOR_LETTER_Z = 122;
 
/**
* Gets the missing letters of a sentence in lower case.
* @param sentence
* @return String having all the letters that the sentence is missing from the alphabet.
*/
public String getMissingLetters(String sentence){
/*
 * 1. Let's populate a set with the unique characters of the sentence.
 *    This approach avoids having two nested for's in the code (better performance).
 */
Set<Integer> uniqueASCIICodes = new HashSet<Integer>();
 
for (char character : sentence.toLowerCase().toCharArray() ) {
 if (character >= ASCII_CODE_FOR_LETTER_A
   && character <= ASCII_CODE_FOR_LETTER_Z) { // Range of lower case letters.
  uniqueASCIICodes.add((int)character);
 
  if (uniqueASCIICodes.size() == 26) {
   break; // Sentence already covered all letter from the alphabet.
  }
 }
}
/*
 * 2. Move in the range of ascii codes of lower case alphabet
 * and check if letter was present in sentence.
 */
StringBuilder misingLettersBuilder = new StringBuilder();
 
for (int i=ASCII_CODE_FOR_LETTER_A; i <= ASCII_CODE_FOR_LETTER_Z; i++) {
 if (!uniqueASCIICodes.contains(i)) {
  misingLettersBuilder.append((char)i);
 }
}
   return misingLettersBuilder.toString();
}
 
public static void main(String[] args) {

   String case1 = "A quick brown fox jumps over the lazy dog";
   String case2 = "bjkmqz";
   String case3 = "cfjkpquvwxz";
   String case4 = "";
 
   MissingLetters missingLetters = new MissingLetters();
 
  System.out.println("Missing letters for[" + case1 + "]: " +
  missingLetters.getMissingLetters(case1));
  System.out.println("Missing letters for[" + case2 + "]: " +
  missingLetters.getMissingLetters(case2));
  System.out.println("Missing letters for[" + case3 + "]: " +
  missingLetters.getMissingLetters(case3));
  System.out.println("Missing letters for[" + case4 + "]: " +
  missingLetters.getMissingLetters(case4));
   }
}
This will be the program output:
Missing letters for[A quick brown fox jumps over the lazy dog]: 
Missing letters for[bjkmqz]: acdefghilnoprstuvwxy
Missing letters for[cfjkpquvwxz]: abdeghilmnorsty
Missing letters for[]: abcdefghijklmnopqrstuvwxyz

1 comment:

  1. I think that if you want to improve performance you should also create an ASCII code Array containing the int from 97 to 122. In fact, you could add that array as a parameter, in case that you want to ignore some letters.

    ReplyDelete