Teaching Kids Programming – Check if the Sentence Is Pangram

Teaching Kids Programming: Videos on Data Structures and Algorithms

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:
Input: sentence = “thequickbrownfoxjumpsoverthelazydog”
Output: true
Explanation: sentence contains at least one of every letter of the English alphabet.

Example 2:
Input: sentence = “leetcode”
Output: false

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

Hints:
Iterate over the string and mark each character as found (using a boolean array, bitmask, or any other similar way).
Check if the number of found characters equals the alphabet length.

Pangram Check Algorithm

Given the input string only contains lowercase characters – we can add all the characters in a Counter or set and check if it is length 26:

1
2
3
4

class Solution:
    def checkIfPangram(self, sentence: str) -> bool:
        x = Counter(sentence)
        return len(x) == 26

class Solution:
    def checkIfPangram(self, sentence: str) -> bool:
        x = Counter(sentence)
        return len(x) == 26

Using Set:

1
2
3

class Solution:
    def checkIfPangram(self, sentence: str) -> bool:
        return len(set(sentence)) == 26

class Solution:
    def checkIfPangram(self, sentence: str) -> bool:
        return len(set(sentence)) == 26

If all characters are allowed, we can bruteforce – checking from ‘a’ to ‘z’ to see if they all are in the sentence:

1
2
3
4
5
6

class Solution:
    def checkIfPangram(self, sentence: str) -> bool:
        for i in range(26):
            if chr(i + 97) not in sentence:
                return False
        return True

class Solution:
    def checkIfPangram(self, sentence: str) -> bool:
        for i in range(26):
            if chr(i + 97) not in sentence:
                return False
        return True

Checking character in string takes O(N) – and thus this solution takes O(26.N) time. But we can use hash table (e.g. Counter, or set) to achieve O(1) lookup – O(N+26) time which is O(N):

1
2
3
4
5
6
7

class Solution:
    def checkIfPangram(self, sentence: str) -> bool:
        c = set(sentence)
        for i in range(26):
            if chr(i + 97) not in c:
                return False
        return True

class Solution:
    def checkIfPangram(self, sentence: str) -> bool:
        c = set(sentence)
        for i in range(26):
            if chr(i + 97) not in c:
                return False
        return True

Or, we can explicitly count the number of occurences O(N+26) time:

1
2
3
4
5
6
7

class Solution:
    def checkIfPangram(self, sentence: str) -> bool:
        c = Counter(sentence)
        for i in range(26):
            if c[chr(i + 97)] == 0:
                return False
        return True

class Solution:
    def checkIfPangram(self, sentence: str) -> bool:
        c = Counter(sentence)
        for i in range(26):
            if c[chr(i + 97)] == 0:
                return False
        return True

We can exit early if there are less than 26 characters in the sentence:

1
2

if len(sentence) < 26:
   return False

if len(sentence) < 26:
   return False

See also: GoLang: Check if the Sentence Is Pangram

–EOF (The Ultimate Computing & Technology Blog) —