1832. Check if the Sentence Is Pangram

EasyHash TableString
Leetcode Link

Problem Description

A pangram is a special kind of sentence in which every letter of the English alphabet is used at least once. The task is to determine whether a given sentence meets the criteria to be a pangram. The input is a string named sentence which consists solely of lowercase English letters. The expected output is a boolean value: true if the given sentence is a pangram, and false otherwise.

Intuition

The intuition behind the solution is to leverage the fact that there are 26 letters in the English alphabet. To verify if a sentence is a pangram, we need to check that each of these letters appears at least once. Using a set is a smart approach because a set automatically filters out duplicate elements. When we convert the sentence into a set, any repeated letters are removed, leaving us with a set of unique characters.

By checking the number of unique characters (the length of the set), we can ascertain whether all 26 letters of the alphabet are present. If the unique character count is precisely 26, it means every letter of the alphabet is represented in the sentence, and hence, the sentence is a pangram. The provided solution code succinctly does this check in one line by comparing the length of the set derived from sentence against the number 26. If they match, true is returned; otherwise false.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Solution Approach

The solution's implementation is straightforward and utilizes Python's built-in data structure—a set—and its characteristics to solve the problem efficiently. The key points of the approach are:

  1. Use of a Set: A set is chosen because it automatically handles the removal of duplicate characters. When we cast the sentence string to a set, all duplicate letters are removed, leaving us with only unique characters. This is done with set(sentence).

  2. Count Unique Characters: After creating a set of unique characters, we simply count how many unique characters are contained in it. This is achieved by calling len(set(sentence)). The len function returns the count of how many elements (in this case, unique letters) are in the set.

  3. Comparison with Alphabet Length: The final step is to compare this count of unique characters to the total number of letters in the English alphabet, which is 26. If the sentence contains every letter of the alphabet at least once, then len(set(sentence)) should be equal to 26.

  4. Return the Result: The comparison len(set(sentence)) == 26 will yield a boolean value (True or False). If the count is 26, it will return True, indicating that the sentence is a pangram. Otherwise, if any letter is missing, and the count is less than 26, the result will be False, indicating that the sentence is not a pangram.

  5. One-Line Solution: The implementation combines these steps into a single line. By returning the result of the comparison directly, the solution becomes both concise and efficient.

Thus, the solution effectively leverages the properties of sets to eliminate redundant operations or the need for explicit loops, resulting in a lean and performant algorithm for checking whether a given sentence is a pangram.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

Example Walkthrough

Let's take a sentence sentence = "the quick brown fox jumps over a lazy dog" and walk through the process to determine if it's a pangram:

  1. Use of a Set: First, convert the sentence into a set of unique characters: unique_chars = set(sentence). The set now contains each character from the sentence without any duplicates.

  2. Count Unique Characters: Count how many unique characters are in the set: unique_count = len(unique_chars). Assuming the sentence is indeed a pangram, the count should include 26 letters plus any additional unique characters like spaces or punctuation marks.

  3. Comparison with Alphabet Length: Now compare this count of unique characters (excluding spaces and punctuation) with the English alphabet's 26 letters. Since we are only interested in the letters, if we had other characters, we would ignore them. But since the sentence is constructed with only letters and spaces, and we can ignore spaces in our count, a direct comparison can be made: is_pangram = (unique_count == 26).

  4. Return the Result: Finally, the result of the comparison will be a boolean value. If unique_count equals 26, is_pangram will be True, indicating that the sentence contains every letter of the English alphabet at least once. Otherwise, it will be False.

Following the given sentence, when we apply the solution, we find that after removing duplicates and excluding spaces, the set contains exactly 26 letters. So len(set(sentence)) equals 26, and the sentence is confirmed to be a pangram, hence True is returned.

Solution Implementation

1class Solution:
2    def checkIfPangram(self, sentence: str) -> bool:
3        # A pangram is a sentence containing every letter of the alphabet at least once.
4        # To check if a sentence is a pangram, we convert the sentence into a set of characters.
5        # A set in Python is a collection data type that is unordered, mutable, and does not allow duplicates.
6        # Therefore, converting the sentence into a set removes any duplicate characters.
7
8        unique_characters = set(sentence)
9
10        # We then check if the number of unique characters is 26, which is the number of letters in the English alphabet.
11        # If there are 26 unique characters, then the sentence must be a pangram and we return True.
12        # Otherwise, we return False as the sentence is missing one or more letters.
13
14        is_pangram = len(unique_characters) == 26
15
16        return is_pangram
17
1class Solution {
2    // Checks if the input string is a pangram (contains all letters of the alphabet at least once)
3    public boolean checkIfPangram(String sentence) {
4        int alphabetMask = 0; // Used to track the presence of each letter
5
6        // Iterate over each character in the sentence
7        for (int i = 0; i < sentence.length(); i++) {
8            // Update the alphabetMask by setting the bit corresponding to the current character
9            // The bit position is determined by subtracting the ASCII value of 'a' from the character
10            alphabetMask |= 1 << (sentence.charAt(i) - 'a');
11        }
12      
13        // The sentence is a pangram if alphabetMask has 26 bits set (one for each letter of the alphabet)
14        // (1 << 26) - 1 creates a mask with 26 bits set to 1
15        return alphabetMask == (1 << 26) - 1;
16    }
17}
18
1#include <string>
2
3class Solution {
4public:
5    bool checkIfPangram(const std::string& sentence) {
6        // Initialize a variable to keep track of the presence of each letter
7        // by using a bit mask. Each bit from 0 to 25 will correspond to
8        // the letters 'a' through 'z'.
9        int letterMask = 0;
10
11        // Iterate through each character in the sentence
12        for (const char& currentChar : sentence) {
13            // Calculate the bit number that represents the current character
14            // by subtracting 'a' from it, and then set that bit in letterMask
15            // using bitwise OR and bit shift left operations.
16            letterMask |= 1 << (currentChar - 'a');
17        }
18
19        // Check if letterMask has all 26 bits set, which means all letters
20        // from 'a' to 'z' are present. A mask with all 26 bits set represents
21        // the number (2^26) - 1. If letterMask is equal to this number, then
22        // the sentence is a pangram.
23        return letterMask == (1 << 26) - 1;
24    }
25};
26
27// Usage example:
28// Solution sol;
29// bool isPangram = sol.checkIfPangram("the quick brown fox jumps over a lazy dog");
30
1function checkIfPangram(sentence: string): boolean {
2    // Initialize a variable to track the letters found in the sentence
3    // Each bit of 'mark' represents one letter of the alphabet
4    let mark = 0;
5
6    // Iterate over each character in the sentence
7    for (const char of sentence) {
8        // Calculate the alphabet index relative to 'a'
9        // 'a' will be 0, 'b' will be 1 and so on
10        const alphabetIndex = char.charCodeAt(0) - 'a'.charCodeAt(0);
11      
12        // Set the bit at the alphabet index to 1
13        // This uses a bitwise OR assignment to mark the presence of the character
14        mark |= 1 << alphabetIndex;
15    }
16
17    // Check if all 26 bits are set to 1
18    // (1 << 26) creates a number with 26 0s followed by a 1
19    // Subtracting 1 from that number flips all 26 0s to 1s
20    // Comparing 'mark' to this value verifies if all letters of the alphabet are present
21    return mark === (1 << 26) - 1;
22}
23
Not Sure What to Study? Take the 2-min Quiz：

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Time and Space Complexity

The time complexity of the provided code is O(N), where N is the length of the input string sentence. This is because constructing a set from the string requires iterating over each character in the string once to produce a set of unique characters.

The space complexity of the code is also O(N), assuming that in the worst case, there are no duplicate characters in the string. The size of the set data structure would grow linearly with the size of the input string up to 26, as there are a maximum of 26 different lower-case English letters. The space complexity becomes constant O(1) when considering that we have a fixed upper limit on the size of the set (26 characters), if we evaluate the space complexity as a function of the character set size rather than the string length.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫