Efficient way to Finding string in python

Question

You are given two strings, AA and BB. Find if there is a substring that appears in both AA and BB.

All the strings contain only lowercase Latin letters.

Above, you see a question from hackerranck. I wrote the following program to solve it:

T = int(raw_input())

for t in xrange(T):
    s1 = raw_input()
    s2 = raw_input()
    length1 = len(s1)
    length2 = len(s2)
    checked = list()
    if length1<length2:
        for letter in s1:
            if len(checked)== 26:
                break
            if letter in checked:
                next
            checked.append(letter)
            if letter in s2:
                print "YES"
                break
        else:
            print "NO"
    else:
        for letter in s2:
            if letter in checked:
                next
            if len(checked)==26:
                break
            checked.append(letter)
            if letter in s1:
                print "YES"
                break
        else:
            print "NO"

It worked correct before adding if len(checked)==26: break. I added this line to make it more efficient by checking each alphabetic letter only once and get rid of time-out error in the submitting process, but after adding this line, the answer of my program is wrong for some test cases. why?

Martijn Pieters · Accepted Answer · 2016-04-11 06:55:30Z

2

Your error is here:

if letter in checked:
    next

next is a function in Python. Using if letter in checked: next is a no-op, you could just as well have used pass, as that will just reference the function object and not call it. It certainly won't continue to the next loop iteration.

So no matter what the outcome of letter in checked is, you continue to add letter to checked. Since checked is a list, not a set, you'll be adding duplicates to the list and you end up with more than 26 entries quite easily.

Use:

if letter in checked:
    continue

and consider using a set for checked to make in membership testing an O(1) operation rather than O(N).

Speaking of sets, this is basically a set intersection problem; is there any single letter that appears in both s1 and s2. You are correctly testing if the sets are disjoint; so use the Python built-in set type. This would in the worst case do an O(N * M) loop, but the looping is in C code:

print('NO' if set(s1).isdisjoint(s2) else 'YES')

By using set.isdisjoint() no new set is created, only a boolean is returned. set(s1) loops over all of s1 to produce the set, set.isdisjoint() will exit early as soon as it finds a match, each match test is O(1) against the set.

You could see if swapping s1 and s2 based on length improves your timings for the test still:

if len(s1) > len(s2):
    s1, s2 = s2, s1
print('NO' if set(s1).isdisjoint(s2) else 'YES')

edited Apr 11, 2016 at 6:55

answered Apr 11, 2016 at 6:45

Martijn Pieters

1.1m326 gold badges4.2k silver badges3.4k bronze badges

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

4 Comments

Ebrahim Ghasemi Over a year ago

Thank you. Sorry I didn't got this: consider using a set for checked to make in membership testing. May I ask you to explain a little more about sets using a sample code or refer me to a article about it please?

Martijn Pieters Over a year ago

@Abraham: docs.python.org/2/library/stdtypes.html#set-types-set-frozenset and wiki.python.org/moin/TimeComplexity; Python lists take O(N) time to test if an element is present, sets can do it in constant time.

Martijn Pieters Over a year ago

@Abraham: so checked = set() to create the set and checked.add(letter) to add a new letter to that set. if letter in checked: continue to skip the loop because you already tested the letter.

Alexander Over a year ago

Didn't realize isdisjoint() existed. Good answer!

Alexander · Accepted Answer · 2016-04-11 06:56:32Z

1

You can use sets and see if the intersection is greater than zero:

"yes" if set(s1).intersection(s2) else "no"

To avoid iterating over the entire list:

"yes" if any(c in s1 for c in s2) else "no"

Depending on the size of s1 and s2 you could possibly benefit from shrinking them to sets:

"yes" if any(c in set(s1) for c in set(s2)) else "no"

edited Apr 11, 2016 at 6:56

answered Apr 11, 2016 at 6:45

Alexander

111k32 gold badges212 silver badges208 bronze badges

Collectives™ on Stack Overflow

Efficient way to Finding string in python

2 Answers 2

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related