Section 2.4.1 - Anagram Detection - Checking Off Solution

[Lespernater]

Firstly, thank you for an amazing resource and for making it open source! I am currently in a compsci course on problem solving using algorithms and was working through the Anagram detection section 2.4.1.

`

def anagramSolution1(s1,s2):
    if len(s1) != len(s2):
        stillOK = False

    alist = list(s2)

    pos1 = 0
    stillOK = True

    while pos1 < len(s1) and stillOK:
        pos2 = 0
        found = False
        while pos2 < len(alist) and not found:
            if s1[pos1] == alist[pos2]:
                found = True
            else:
                pos2 = pos2 + 1

        if found:
            alist[pos2] = None
        else:
            stillOK = False

        pos1 = pos1 + 1

    return stillOK

print(anagramSolution1('abcd','dcbka')) # This returns True

`

It seems a small semantic error that has no bearing on the Big-O analysis that follows (so I'm sorry) but anagramSolution1 will return True even if sequences have different lengths. Changing line 3 from stillOK = False to return False resolves this.

`

def anagramSolution1(s1,s2):
    if len(s1) != len(s2):
        return False

    alist = list(s2)

    pos1 = 0
    stillOK = True

    while pos1 < len(s1) and stillOK:
        pos2 = 0
        found = False
        while pos2 < len(alist) and not found:
            if s1[pos1] == alist[pos2]:
                found = True
            else:
                pos2 = pos2 + 1

        if found:
            alist[pos2] = None
        else:
            stillOK = False

        pos1 = pos1 + 1

    return stillOK

print(anagramSolution1('abcd','dcbka')) # This returns False

` My apologies if this has already been spotted and resolved, I didn't see any reference to this in the open or closed issues.

[bnmnetp]

Thanks for spotting this. I'll try to get the fix in by Saturday.

[KavehVasei]

Thanks for fixing the bug in the first solution on section 3.4.1. On the same note the solution 2 on section 3.4.2 also needs to check for the lengths: ` def anagramSolution2(s1,s2): alist1 = list(s1) alist2 = list(s2)

alist1.sort()
alist2.sort()

pos = 0
matches = True
######### we can add here
#### if len(alist1) != len(alist2): matches=False

while pos < len(s1) and matches:
    if alist1[pos]==alist2[pos]:
        pos = pos + 1
    else:
        matches = False

return matches

print(anagramSolution2('abcde','edcbazygjlf')) ## this also returns true! `

[bnmnetp]

I have not read through the text in a LONG time, but I believe we say in the text that we are making the assumption that the strings are the same length.

Yep, I just checked....

For the sake of simplicity, we will assume that the two strings in question are of equal length and that they are made up of symbols from the set of 26 lowercase alphabetic characters.