Creating a dictionary of all prefixes of a string in Python

Question

a=raw_input()
prefix_dict = {}
for j in xrange(1,len(a)+1):
    prefix = a[:j]
    prefix_dict[prefix] = len(prefix)
print prefix_dict

Is there any possibility of memory error in the above code?

Answer 1

It's hard to tell what is making the error occur without giving us the input, but it's certainly possible the input is too large for the system to store.

prefix_dict will contain len(a) entries so if your input is larger than 32-bit python allows for dictionary size on your machine, then that could be the issue.

I will note that instead of having prefix_dict[prefix] = len(prefix) you could just have prefix_dict[prefix] = j which would stop you from needing to do an extra length calculation each time (not that this would be the cause of the memory issue).

Take a look at the sample output (I modified the print statement and used an example string):

>>> prefix_dict = {}
>>> a = 'hello'
>>> for j in xrange(1,len(a)+1):
        prefix = a[:j]
        prefix_dict[prefix] = len(prefix)
        print j, len(prefix), prefix_dict

1 1 {'h': 1}
2 2 {'h': 1, 'he': 2}
3 3 {'hel': 3, 'h': 1, 'he': 2}
4 4 {'hel': 3, 'h': 1, 'hell': 4, 'he': 2}
5 5 {'hel': 3, 'h': 1, 'hell': 4, 'hello': 5, 'he': 2}

Answer 2

The slice operator in a[:j] creates a copy of the sublist so is perfectly possible that you get a MemoryError.