CODEWITHSUNDEEP
pythonrecursionvariable-assignmentanagram
Tytire Recubans
Tytire Recubans

Reputation: 997

find anagrams in a list of string using recursive solution in python

I am trying to solve the following problem: there is a list like the below:

["hi", "ih", "ciao", "aoic", "bar", "foo", "rab", "oof"]

And after being passed to a function, the list should be reduced to only those elements which first appear in the list, excluding all their anagrams after them.

so it should output:

["hi", "ciao", "bar", "foo"]

I am trying to solve this recursively, and have the current solution, which breaks because of a "referenced before assignment" error on the variable result (last return stmt).

I am very grateful for any hint!

def f(ls):
        
    def is_not_ana(first, word):
        return not sorted(first) == sorted(word) and word or None
    
    if ls:
        first = ls[0]
        rest = ls[1:]
        legal_str = [is_not_ana(first, word) for word in rest]
        result = list(filter(None, [first] + legal_str))
        
        return f(result[1:])
    else:
        return result

Upvotes: 0

Views: 535

Answers (1)

Dorian Turba
Dorian Turba

Reputation: 3745

When you reach the end of your recursive, ls is empty, so when you return result, it is never defined in this last call.

You forgot to return the first. Change return f(result[1:]) to return [first] + f(result[1:]).

Return an empty list will fix your error:

def f(ls):
    def is_not_ana(first, word):
        return not sorted(first) == sorted(word) and word or None

    if ls:
        first = ls[0]
        rest = ls[1:]
        legal_str = [is_not_ana(first, word) for word in rest]
        result = list(filter(None, [first] + legal_str))

        return [first] + f(result[1:])
    else:
        return []


print(f(["hi", "ih", "ciao", "aoic", "bar", "foo", "rab", "oof"]))
# ['hi', 'ciao', 'bar', 'foo']

Upvotes: 2

Related Questions