3
\$\begingroup\$

Given

Roy wanted to increase his typing speed for programming contests. So, his friend advised him to type the sentence "The quick brown fox jumps over the lazy dog" repeatedly, because it is a pangram. (Pangrams are sentences constructed by using every letter of the alphabet at least once.) After typing the sentence several times, Roy became bored with it. So he started to look for other pangrams. Given a sentence s, tell Roy if it is a pangram or not. Input Format Input consists of a line containing s.

Constraints

Length of s can be at most 103 \$(1≤|s|≤103)\$ and it may contain spaces, lower case and upper case letters. Lower case and upper case instances of a letter are considered the same.

Solution 1

from collections import defaultdict
import string

def is_pangram(astr):
    lookup = defaultdict(int)

    for char in astr:
        lookup[char.lower()] += 1        
    for char in string.ascii_lowercase:
        if lookup[char] == 0:
            return False
    return True

print "pangram" if is_pangram(raw_input()) else "not pangram"

Solution 2

from collections import Counter
import string

def is_pangram(astr):
    counter = Counter(astr.lower())
    for char in string.ascii_lowercase:
        if counter[char] == 0:
            return False
    return True

print "pangram" if is_pangram(raw_input()) else "not pangram"

Which is better in terms of running time and space complexity?

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Have you benchmarked them? What did it say? \$\endgroup\$
    – Mast
    Sep 23 '15 at 8:31
5
\$\begingroup\$

Since you do not actually need the count of each character, it would be simpler to use a set and the superset operator >=:

def is_pangram(astr):
    return set(astr.lower()) >= set(string.ascii_lowercase):


Your two solutions are almost identical, though here

for char in astr:
    lookup[char.lower()] += 1  

it would be faster to lowercase the whole string at once (like you already do in solution 2):

for char in astr.lower():
    lookup[char] += 1  

Other than that, the only difference is defaultdict vs. Counter. The latter makes your code more elegant, but since the standard library implements Counter in pure Python, there may be a speed advantage to defaultdict.

\$\endgroup\$
5
  • \$\begingroup\$ Two things, you say Counter is faster than defaultdict, right? Second, you say that lowercasing whole string is faster but why? \$\endgroup\$
    – CodeYogi
    Nov 6 '15 at 16:17
  • \$\begingroup\$ What is the significance of the maximum length 103 on the string. \$\endgroup\$
    – CodeYogi
    Nov 6 '15 at 16:18
  • \$\begingroup\$ Got the answer, defaultdict is implemented in c hence its faster than Counter. \$\endgroup\$
    – CodeYogi
    Nov 6 '15 at 16:30
  • \$\begingroup\$ @CodeYogi A single call to the lower method is faster than many calls of the same, especially because the actual lowercasing of each string happens in a fast C loop. I don't know where the 103 comes from, but Google tells me that there is a Guinness world record for typing 103 characters with the nose: guinnessworldrecords.com/news/2015/9/… \$\endgroup\$ Nov 6 '15 at 16:48
  • \$\begingroup\$ Hmm, strange (for the record part)! \$\endgroup\$
    – CodeYogi
    Nov 6 '15 at 16:50
3
\$\begingroup\$

This one requires only one integer of storage:

    ord_a = 97 # ord('a')
    ord_z = 122 # ord('z')

    def is_pangram(s):
      found = 0
      for c in s:
        ord_char = ord(c.lower())
        if ord_a <= ord_char <= ord_z:
          found |= 1 << (ord_char - ord_a)
      return found == (1 << 26) - 1

The data structure used is the integer found, whose least significant 26 bits are used to indicate if the corresponding letter has been found. The coding is simply a=0, b=1, etc, which can be conveniently done obtained from the ASCII code as ord(char) - ord('a'). The characters in the string have to be iterated, if you wish you could stop when you found them all.

Note that even though the algorithmic complexity is essentially the lowest possible, the fact that the loop is in pure Python makes it slower than one which avoids looping in Python, even if it has to perform more operations.

\$\endgroup\$
0
2
\$\begingroup\$

Both are too slow since you don't need to care about the amount but you're storing a count of each letter anyway. You just need to know if all of the relevant characters are in the string. You can do this easier, faster and with less memory usage by calling all.

def is_pangram(astr):
    return all(char in astr.lower() for char in string.ascii_lowercase)

This will just check each character in ascii_lowercase and see if it's in astr. No need to store values at all, and this supports shortcircuiting. Short circuiting will prematurely end a test if it realises that it already has its result.

So the script will run through and might find an a, b, c, d, and e. But then maybe it can't find an f in the string, instead of continuing to check for g it will immediately return False at that point because it already knows that one letter is missing, so the expression can't be True. This saves on time since the rest of the checks are redundant for the result you want.

\$\endgroup\$
9
  • 1
    \$\begingroup\$ What do you mean by shortcircuiting? can you please explain me a bit? \$\endgroup\$
    – CodeYogi
    Sep 23 '15 at 9:04
  • \$\begingroup\$ @CodeYogi I added an explanation, let me know if it's not quite clear enough! \$\endgroup\$ Sep 23 '15 at 9:08
  • \$\begingroup\$ Hmm, there is something wrong, for each letter it will do the linear search in ascii_lowercase so, it seems to be slow. \$\endgroup\$
    – CodeYogi
    Sep 23 '15 at 13:36
  • \$\begingroup\$ @CodeYogi I'm running benchmarks and that's not what I've found. My answer seems seven times faster than both yours, have you tested it? It's also even faster if you make the string a set as @JanneKarila suggested. \$\endgroup\$ Sep 23 '15 at 14:21
  • \$\begingroup\$ No, but logically I am correct. Now its a totally different story how the language has implemented its operations internally. And most of the time we first solve the problem on paper before typing it down. \$\endgroup\$
    – CodeYogi
    Sep 24 '15 at 1:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.