7
\$\begingroup\$

Here is the code I wrote for the problem at http://www.interviewstreet.com/recruit/challenges/solve/view/4e1491425cf10/4efa210eb70ac where we need to to print the substring at a particular index from the lexicographicaly-sorted union of sets of substrings of the given set of strings...

import itertools
N = int(raw_input())
S = set()
for n in xrange(N):
    W = raw_input()
    L = len(W)
    for l in xrange(1,L+1):
        S=S.union(set(itertools.combinations(W, l)))
        print set(itertools.combinations(W, l))
print S
M = int(raw_input())
S = sorted(list(S))
print S
for m in xrange(M):
    Q = int(raw_input())
    try:
        print "".join(S[Q-1])
    except:
        print "INVALID"

but it gives me a Memory Error meaning that my code takes up more than 256Mb during execution.

I think the culprit is S=S.union(set(itertools.combinations(W, l))), but can't really think of a more efficient method for harvesting a unique set of substrings from the given set of strings...

Can you suggest an optimal alternative?

\$\endgroup\$
1
  • 1
    \$\begingroup\$ For starters, type this at the python prompt >>> import itertools >>> for i in itertools.combinations("ABCDE",3): ... print i. Getting just what you want? Then you may want to review your definition of substring (and/or contiguous). \$\endgroup\$ Jan 19, 2012 at 4:28

1 Answer 1

4
\$\begingroup\$

To successfully pass all test cases you need to implement something more sophisticated like suffix tree. That will allow you to solve this task in O(n) time using O(n) space.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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