What is a Pangram?
A pangram is a sentence containing every letter of the alphabets. Our job today is to try to find if the given string is a pangram or not. This will be an O(n) time and O(2n) space complexity problem with n being the length of the string. Reason being that we need to traverse the string all the way to understand if all the alphabets are in the string or not. One can add an exit condition where if the pangram is found, we ignore the rest of the string but again, that means we put in additional checks after each find of an alphabet. Not worth the extra computations required except if we are talking of very big strings. Lets try to tackle that in part 2.
Our simple code converts all the characters in a given string to lower case first. We use the std::transform function in <algorithms> to do that. We also have initially declared a map of all the alphabets with value set to false. Now our task is pretty simple. We iterate through the string and mark the value of the alphabet in the map (i.e. change it to true) if that alphabet is encountered in the map. Accessing map elements is pretty fast with a runtime complexity of O(1). Similarly, accessing array elements in string is O(1). We need to iterate over the whole string. Lastly, we iterate over our map and see if all the elements are set to true. If yes, the string is a pangram otherwise it is not.
Code to find if sentence is pangram or not?
Remember that we skip constants in calculating space and time complexity. Time complexity in this case is O(n) and space complexity is O(2N).
This post is contributed by Naresh, please contact us if you are willing to contribute to algorithms and me.