Sunday, April 22, 2018

How will you check if a given sentence is a pangram or not

Pangram
A pangram is a sentence containing every letter in the English Alphabet (a-z).
Pangram example: The quick brown fox jumps over the lazy dog
Pack my box with five dozen liquor jugs.
— Pangram
Approach:
  1. Create an boolean array that can hold 26 boolean corresponding to each alphabet in English.
  2. Traverse each character of the sentence and mark corresponding index (a=0, b=1,.. z=26) in the boolean array. Take care of upper and lower case.
  3. Traverse through the entire boolean array and see if all characters are covered. If all positions are set to true then input sentence is a pangram.
Pangram Source
package org.shunya.interview.chapter2;

public class Pangram {

    public boolean checkPangram(String str) {
        boolean[] mark = new boolean[26];

        int index = 0;
        for (int i = 0; i < str.length(); i++) {
            // If uppercase character, subtract 'A' to find index.
            if ('A' <= str.charAt(i) && str.charAt(i) <= 'Z')
                index = str.charAt(i) - 'A';
            else if ('a' <= str.charAt(i) && str.charAt(i) <= 'z')
                index = str.charAt(i) - 'a';
            mark[index] = true;
        }
        for (int i = 0; i <= 25; i++)
            if (!mark[i])
                return (false);
        return (true);
    }
}
A slightly optimized version of the same program can use an integer (has 32 bits) to hold the state of 26 alphabets by use of Bitwise OR and left shift operator.
 private void pangramEfficient() {
        String s = "The quick brown fox jumps over the lazy dog";
        int i = 0;
        for (char c : s.toCharArray()) {
            int x = Character.toUpperCase(c);
            if (x >= 'A' && x <= 'Z') {
                i |= 1 << (x - 'A');
            }
        }
        if (i == (1 << (1 + 'Z' - 'A')) - 1) {
            System.out.println("input is a pangram");
        } else {
            System.out.println("input is not a pangram");
        }
    }
JUNIT Test
import org.junit.Test;

import static org.junit.Assert.assertTrue;

public class PangramTest {
    private Pangram pangramChecker = new Pangram();

    @Test
    public void checkPangram() {
        String str = "The quick brown fox jumps over the lazy dog";
        assertTrue(pangramChecker.checkPangram(str));
    }
}
Thats all.

For more such questions, you can get my ebook

Cracking Core Java Interviews
Buy from Shunya @ 250 ₹ (DRM Free)
Buy from Pothi.com

No comments:

Post a Comment

Your comment will be published after review from moderator