Python Programming Challenges for beginners?
Lie Ryan
lie.1296 at gmail.com
Sat Nov 28 19:24:24 CET 2009
On 11/28/2009 1:51 AM, n00m wrote:
> On Nov 27, 1:22 pm, Jon Clements<jon... at googlemail.com> wrote:
>> Of course, if you take '~' literally (len(s)<= -10001) I reckon
>> you've got way too many :)
>>
>> Jon.
>
> Then better: len(s)< abs(~10000)
>
> PS It's a hard problem; so let's leave it alone
I'm not going to write it, but I guess a fairly efficient solution can
be written with using a Trie: http://en.wikipedia.org/wiki/Trie
and iterating over its items, including partial prefixes.
Worse case scenario for creating the tree would be O(n**2) where n =
length of string, and iterating the structure would take O(N) where N =
number of different substring.
for "abbaz", the data structure would be:
{'a': {'b': {'b': {'a': {'z': None}}},
'z': None,
},
'b': {'b': {'a': {'z': None}},
'a': {'z': None}},
},
'z': None,
}
iterating the structure:
a
ab
abb
abba
abbaz
az
b
bb
bba
bbaz
ba
baz
z
---
13 (not including '')
Now, this makes me interested. How efficient it would be when len(s) ==
10000... might as well write it and see. Take back what I said, give me
a minute...
More information about the Python-list
mailing list