CODEWITHSUNDEEP
python
user3636636
user3636636

Reputation: 2499

Finding suffixes in a set of strings, Python

Given an input - words as a set of strings - determine whether any of the words contained in the set are suffixes of other words in the set, returning True if so, and False if not.

Methods i have tried:

import re
def findsuffix(words_set):
    for i in words_set:
        x = re.compile('w*'+i)
        for j in words_set:
            while i != j:
                if x.search(j):
                    return True
                else
                    return False

I have also tried .endswith() option.

I am relatively new and still learning, i think it is iterating through the words set that i am having issues with. Any help would be appreciated. Thanks

Upvotes: 0

Views: 2362

Answers (3)

Eastsun
Eastsun

Reputation: 18869

Here is my solution, (with O(n log n) time complexity rather than O(n*n) ):

def findsuffix(word_set):
    ws = sorted(w[::-1] for w in word_set)
    return any(y.startswith(x) for x, y in zip(ws[:-1], ws[1:]))

findsuffix(['abcdef', '123', 'cdef'])
Out[1]: True

findsuffix(['abcdef', '123', 'cdefg'])
Out[2]: False

Upvotes: 3

vil
vil

Reputation: 947

def findsuffix(words_set):
    words_set = set(words_set)
    for i in words_set:
        for j in words_set:
            if i == j:
                continue
            if i.endswith(j) or j.endswith(i):
                return True
    return False

Upvotes: 1

abarnert
abarnert

Reputation: 366013

endswith would be fine—and a lot simpler, and probably even faster. But that's not the main problem with your code.

The first problem is here:

if x.search(j):
    return True
else
    return False

The first time you find a pair that isn't a match, you're going to return False immediately, without testing any other pairs of words. But you only want to return False if all pairs are not matches, not if any pair is not a match.

To fix this, just remove that else clause, and put a return False after the whole top-level loop.

But you have another problem you also have to fix:

while i != j:

Since you don't reassign or modify i or j anywhere in that loop, once i != j is true once, it'll be true forever. So, you're going to loop forever, testing the same two values.

What you want here is an if statement:

if i != j:

It would really help to learn how to debug your flow control. You can do quick&dirty debugging by adding lines like print('About to check {}'.format(j)) in appropriate places, and seeing what gets printed out. But it's much better to learn to use the debugger, or an online visualizer like this one.

Upvotes: 3

Related Questions