Need help reducing execution time of python code

Question

As the title says i need help reducing the execution time of the code I've written as the online judge I'm compiling it on gives me a time limit exceeded error even though the code seems to work and gives the correct answer when I compile it.

The question:

Compare a list of string and find the number of distinct strings, where two strings are considered to be "identical" (not distinct) if they're exactly the same, or the same but reversed. The strings only contain the letters a-z, are all lowercase, and have at most 10 characters. Each set provided will have at most 5000 strings in it.

For example, the string "abc" is identical to "cba" as well as "abc." The string "cba" is identical to "abc" as well as "cba." The list ["abc," "cba," "bac"] has 2 distinct strings in it.

Write a function answer(x) which takes a list of strings, x, and returns the number of distinct strings using this definition of identical.

My code:

def answer(x):
    b=0
    ph=[]
    rand=0
    for y in x:
        comp=list(y)
        ph.append(comp)
    while b<len(ph)-1:
        j=b+1
        while j<len(ph):

            if(len(ph[b])==len(ph[j])):
                i=0

                while(i<len(ph[b])):

                    if ph[b][i]==ph[j][i]:
                        rand+=1

                    elif ph[b][i]==ph[j][len(ph[b])-1-i]:
                        rand+=1
                        i+=1
                if rand==len(ph[b]):
                    ph.pop(j)
                rand=0
            j+=1
        b+=1

    return len(ph)

This question might be more suitable for CodeReview than StackOverflow, you might get better help there — en_Knight
– en_Knight, Commented Dec 12, 2014 at 23:00
Your code doesn't actually work. Well, technically, it goes into an infinite loop. — jgritty
– jgritty, Commented Dec 12, 2014 at 23:15

nobody · Accepted Answer · 2014-12-12 23:14:54Z

2

Don't need to do a serial character comparison to check for string identity.

Strings are immutable in Python. Just put the string and its reverse in a dictionary, and then always check against that dictionary.

def answer(x):
    seen = {}
    count = 0
    for s in x:
        if s not in seen:
           seen[s] = True
           seen[s[::-1]] = True
           count +=1
    return count

edited Dec 12, 2014 at 23:14

nobody

20.3k17 gold badges59 silver badges80 bronze badges

answered Dec 12, 2014 at 22:53

aa333

2,58419 silver badges23 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Irshad Bhat · Accepted Answer · 2014-12-13 00:19:51Z

0

This could be directly done with set() function with minimum possible time but it will only remove exactly same strings. Thus to remove reversed strings also, a loop is required but before that similar strings (not reversed) are filtered out using set() which highly reduces loop iterations.

>>> def getUnique(st):
...    st = set(st)
...    unique = set()
...    for x in st:
...        if x[::-1] not in unique:
...           unique.add(x)
...    return list(unique)
... 
>>> strings = ['abc','def','ghi','abc','cba','ihg','jkl','lkj','the']
>>> getUnique(strings)
set(['the', 'abc', 'lkj', 'ihg', 'def'])

edited Dec 13, 2014 at 0:19

answered Dec 13, 2014 at 0:13

Irshad Bhat

8,7792 gold badges31 silver badges37 bronze badges

Collectives™ on Stack Overflow

Need help reducing execution time of python code

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related