Description

A pangram is a sentence where every letter of the English alphabet appears at least once.

Given a string sentence containing only lowercase English letters, return true if sentence is a pangram, or false otherwise.

Example 1:

1Input: sentence = "thequickbrownfoxjumpsoverthelazydog"
2Output: true
3Explanation: sentence contains at least one of every letter of the English alphabet.

Example 2:

1Input: sentence = "leetcode"
2Output: false

Constraints:

  • 1 <= sentence.length <= 1000
  • sentence consists of lowercase English letters.

Solution

Here, the sentence consists of only lowercase English letters. That means there are no punctuations or spaces in the string sentence, so we will not have to filter them out, but if this constraint was not there, then we would have to filter out only alphabetic characters. Also ,the problem mentions this consists of only lowercase English letters which means we will not have to care too much about the case of each character. They are all of the same lowercase.

1. Brute Force

The brute force approach for this problem might be to iterate through each character in English alphabet and see if they exist in the current string. This will give us time complexity of O(26 * n) where n is the length of the sentence. The simplest optimization we can do is to check if the sentence is at least 26 characters long. If it’s not, it will definitely not contain all 26 English lowercase letters.

 1class Solution {
 2    public boolean checkIfPangram(String sentence) {
 3        if (sentence.length() < 26) {
 4            return false;
 5        }
 6
 7        for (char c = 'a'; c <= 'z'; c++) {
 8            if (getIndex(sentence, c) < 0) {
 9                return false;
10            }
11        }
12
13        return true;
14    }
15
16    private int getIndex(String sentence, char c) {
17        for (int i = 0; i < sentence.length(); i++) {
18            if (sentence.charAt(i) == c) {
19                return i;
20            }
21        }
22        return -1;
23    }
24}

Here, I have defined getIndex() method, we could also use indexOf() built-in method, but still the that would also take O(n) time resulting in time complexity of O(n ^ 2). To be specific in this case, O(26 * n).

2. Using Array

In this case, we have to have all 26 characters of lowercase English letters. We can keep track of each character in an array data structure, tracking how many times a given character has occurred. This way storing this information is constant time and even retrieving this information is in constant time. However, we do use space of O(26) to store each character frequency. This algorithm gives us time complexity of O(n) even though we have two iterations in it, once through all characters of the sentence and second time through the array which stored the frequency of each character.

 1class Solution {
 2    public boolean checkIfPangram(String sentence) {
 3        if (sentence.length() < 26) {
 4            return false;
 5        }
 6
 7        int[] charCount = new int[26];
 8        for (int i = 0; i < sentence.length(); i++) {
 9            charCount[sentence.charAt(i) - 'a']++;
10        }
11
12        for (int i = 0; i < charCount.length; i++) {
13            if (charCount[i] == 0) {
14                return false;
15            }
16        }
17
18        return true;
19    }
20}

3. Using Hashing

Another potentially cleaner approach would to iterate through sentence. In each iteration, we store the character in HashMap or HashSet. At the end, we have to verify that we have size equal to 26 which means all characters have occurred at least once. Below example uses HashSet but similar logic will apply to HashMap as well.

1class Solution {
2    public boolean checkIfPangram(String sentence) {
3        Set<Character> charSet = new HashSet<>();
4        for (char c: sentence.toCharArray()) {
5            charSet.add(c);
6        }
7        return charSet.size() == 26;
8    }
9}