C++ || 7 different approaches || clean code
\nTitle: C++ || 7 different approaches || clean code\nProblem: 1832\nURL: https://leetcode.com/problems/check-if-the-sentence-is-pangram/discuss/2713135/c-7-dif
<!--\nTitle: C++ || 7 different approaches || clean code\nProblem: 1832\nURL: https://leetcode.com/problems/check-if-the-sentence-is-pangram/discuss/2713135/c-7-different-approaches-clean-code\n-->\n\nI had way too much fun coming up with different approach to solve this problem. Please let me know if you have any suggestions for another approach or on how to improve one of the approach below. ... and leave a like before you go. :)\n\n\n### Approach 1: hash set\n\n```cpp\n    static bool checkIfPangram(const string& s) {\n        const unordered_set<char> seen(begin(s), end(s));\n        return size(seen) == 26;\n    }\n```\n\nThis can be writen as a one-liner as well:\n\n```cpp\n    static bool checkIfPangram(const string& s) {\n        return size(unordered_set<char>{begin(s), end(s)}) == 26;\n    }\n```\n\nWe could also use a ```set```, but since we only care about the since and not the order of elements, this would just make things less efficient.\n\n**Complexity Analysis**\n  * Time complexity: $$O(n)$$ we need to insert all the characters into a hash set, with each insert operation being $$O(1)$$\n  * Space complexity: $$O(1)$$ as the size of the hash set is limited to 26 entries.\n\n### Approach 2: std::sort and std::unique\n\n```cpp\n    static bool checkIfPangram(string& s) {\n        sort(begin(s), end(s));\n        return distance(begin(s), unique(begin(s), end(s))) == 26;\n    }\n```\n\nInstead of modifying the string with ```unique``` again. We could also just count the number of unique elements by comparying adjacent elements, something like the following (kudos to @vonser):\n\n```cpp\n    static bool checkIfPangram(string& s) {\n        sort(begin(s), end(s));\n        int count = 1;\n        for (int i = 1; i < size(s); ++i)\n            if (s[i - 1] != s[i]) ++count;\n        return count == 26;\n    }\n```\n\n**Complexity Analysis**\n  * Time complexity: $$O(n \\log n)$$ for sorting the rest is linear or constant time\n  * Space complexity: $$O(1)$$\n\n\n### Approach 3: brute force with std::string::find\n\n```cpp\n    static bool checkIfPangram(const string& s) {\n        for (char ch = \'a\'; ch <= \'z\'; ++ch)\n            if (s.find(ch) == string::npos) return false;\n\n        return true;\n    }\n```\n\n**Complexity Analysis**\n  * Time complexity: $$O(26 n)$$ which is $$O(n)$$\n  * Space complexity: $$O(1)$$\n\n\n### Approach 4: bit masking and std::accumulate\n\n```cpp\n    static bool checkIfPangram(const string& s) {\n        int seen = 0;\n        for (char ch : s) seen |= 1 << (ch - \'a\');\n        return seen == (1 << 26) - 1;\n    }\n```\n\nWe could add an early exit if we have already seen all different characters:\n\n```cpp\n    static bool checkIfPangram(const string& s) {\n        int seen = 0;\n        int rem = 26;\n        for (char ch : sentence) {\n            int mask = 1 << (ch - \'a\');\n            if (!(seen & mask)) {\n                if (!--rem) return true;\n                seen |= mask;\n            }\n        }\n        return false;\n    }\n```\n\nOr combining the two ideas above:\n\n```cpp\n    static bool checkIfPangram(const string& s) {\n        int seen = 0;\n        for (char ch : s) {\n            seen |= 1 << (ch - \'a\');\n            if (seen == (1 << 26) - 1) return true;\n        }\n        return false;\n    }\n```\n\nWithout raw loops and using ```std::accumulate``` we can turn this into a one-liner (a long though):\n\n```cpp\n    static bool checkIfPangram(const string& s) {\n        return accumulate(begin(s), end(s), 0, [](int seen, char ch) { return seen | (1 << (ch - \'a\')); }) == (1 << 26) - 1;\n    }\n```\n\n**Complexity Analysis**\n  * Time complexity: $$O(n)$$\n  * Space complexity: $$O(1)$$\n\n### Approach 5: std::transform and std::reduce w/ std::bit_or\n\nThis builds on the idea from approach 4. We first transform this into bit masks first and then reduce them. What\'s intersting about ```std::reduce``` is that it coudl be executed in parallel. The down side of this approach is that we need a more extra memory. It should be noted that the reduce step doesn\'t guartee an execution order and this is only correct because ```bit_or``` (```|```) is associative and commutative.\n\n```cpp\n    static bool checkIfPangram(const string& s) {\n        vector<int> tmp(size(s));\n        transform(begin(s), end(s), back_inserter(tmp), [](char ch) { return 1 << (ch - \'a\'); });\n        return reduce(begin(tmp), end(tmp), 0, bit_or{}) == (1 << 26) - 1;\n    }\n```\n\n**Complexity Analsysis**\n  * Time complexity: $$O(n)$$\n  * Space complexity: $$O(n)$$ for the temporary arrary\n\n### Approach 6: std::transform_reduce\n\nThe idea is the same as for approach 5, but we can reduce this to a one-liner w/o temporary memory. As w/ approach 5 this could also be executed in parallel for very large inputs.\n\n```cpp\n    static bool checkIfPangram(const string& s) {\n        return transform_reduce(begin(s), end(s), 0, bit_or{}, [](char ch) { return 1 << (ch - \'a\'); }) == (1 << 26) - 1;\n    }\n```\n\n**Complexity Analsysis**\n  * Time complexity: $$O(n)$$\n  * Space complexity: $$O(1)$$\n\n### Approach 7: array\n\nLast but not least there are several variations of using an array to keep track of the characters we have seen.\n\n```cpp\n    static bool checkIfPangram(const string& s) {\n        array<bool, 26> seen = {};\n        for (char ch : s) seen[ch - \'a\'] = true;\n        // TODO(heder): std::identity is C++ 20. Is there another library function?\n        return all_of(begin(seen), end(seen), [](int x) { return x; });\n    }\n ```\n \n A variation of the above could be the use ```reduce``` / ```accumulate``` instead of ```all_of```. NB. we are using an ```array<char, 26>``` instead of a bool array:\n \n ```cpp\n     static bool checkIfPangram(const string& s) {\n        array<char, 26> seen = {};\n        for (char ch : s) seen[ch - \'a\'] = 1;\n        return reduce(begin(seen), end(seen)) == 26;\n    }\n```\n\nSimilar to the approach with the bit mask, we could also do an early exit here:\n\n```cpp\n    static bool checkIfPangram(const string& s) {\n        array<bool, 128> seen = {};\n        int rem = 26;\n        for (char ch : s) {\n            if (!seen[ch]) {\n                if (!--rem) return true;\n                seen[ch] = true;\n            }\n        }\n        return false;\n    }\n ```\n\n**Complexity Analsysis**\n  * Time complexity: $$O(n)$$\n  * Space complexity: $$O(1)$$\n\n### Appendix\n\nI have seen a few solution how are doing something like ```if (size(sentence) < 26) return false;``` which is a nice optimisation.\n\n_As always: Feedback, questions, and comments are welcome. Leaving an upvote sparks  joy! :)_\n\n**p.s. Join us on the [LeetCode The Hard Way Discord Server](https://discord.gg/hFUyVyWy2E)!**\n
['C', 'C++']