efficiency of algorithm - are all string elements unique

Question

The task: Implement an algorithm to determine if a string has all unique characters.

I wrote two functions that dose that. How do I start to asses which one is better/more efficient? what are the things to look for?

this is the first one:

def is_unique(word):
    start = 0
    len_word = len(word)

    while start < len_word:
        for i in range(start + 1, len_word):
            if word[start] == word[i]:
                return False
        start += 1
    return True

second one:

def unique_list(word):
    unique = []

    for i in word:
        if i in unique:
            return False
        else:
            unique += i
     return True

chqrlie · Accepted Answer · 2020-04-20 10:52:53Z

2

Both algorithms are inefficient: their complexity is O(n^2) with n the number of character in word. The second algorithm will be a bit faster in practice because it uses the build-in Python operation i in unique (rather than slow CPython loops).

The test can be done in a much faster way: len(set(s)) == len(s). This line tests if the string contains unique characters in O(n) (since the string characters can be converted to a set in linear time).

edited Apr 20, 2020 at 10:52

chqrlie

152k12 gold badges145 silver badges231 bronze badges

answered Mar 22, 2020 at 22:31

Jérôme Richard

53.4k6 gold badges48 silver badges77 bronze badges

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

1 Comment

chqrlie Over a year ago

Your solution is so elegant! And the performance must be quite optimal in the general case since all the work is done in the set constructor, implemented in executable code. Yet for long strings with duplicate characters coming early in the string, both approaches by the OP will return false quicker. Constructing the set incrementally might be more appropriate if duplicates are more likely to occur than not.

Collectives™ on Stack Overflow

efficiency of algorithm - are all string elements unique

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related