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?

@JoelCornett The above code is a part of another code from a contest. when tried on the website it gave a memoryerroer at prefix = a[:j] . — sachin irukula
– sachin irukula, Commented Jul 23, 2012 at 16:02
@JoelCornett Sorry, but I lost you "What implementation of python are you using?" do u mean version or anything else?? — sachin irukula
– sachin irukula, Commented Jul 23, 2012 at 17:31
I mean, what are you running this code on? cPython? Jython? Stackless Python? The code as given shouldn't give you an error, so any errors would be platform specific. Are you sending this code to a server? — Joel Cornett
– Joel Cornett, Commented Jul 23, 2012 at 18:31

barracel · Accepted Answer · 2012-11-21 23:50:19Z

1

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

answered Nov 21, 2012 at 23:50

barracel

1911 bronze badge

Add a comment |

Jeremy K · Accepted Answer · 2012-11-22 01:33:53Z

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}

Stack Exchange Network

Creating a dictionary of all prefixes of a string in Python

2 Answers 2

You must log in to answer this question.

Hot Network Questions

Creating a dictionary of all prefixes of a string in Python

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions