Anagram Solutions

Solution 1: Checking off

$\sum_{i=1}^{n} i = \frac{(n)(n+1)}{2} = \frac{1}{2}n^2 + \frac{1}{2}n$ -> $O(n^2)$

In [13]:
def anagram1(s1, s2):
    alist = list(s2)
    pos1 = 0
    still_ok = True
    
    while pos1 < len(s1) and still_ok:
        pos2 = 0
        found = False
        
        while pos2 < len(alist) and not found:
            if s1[pos1] == alist[pos2]:
                found = True
            else:
                pos2 += 1
                
        if found:
            alist[pos2] = None
        else:
            still_ok = False
            
        pos1 += 1
        
    return still_ok
In [14]:
anagram1("python", "typhon")
Out[14]:
True
In [15]:
anagram1("python", "typhonz")
Out[15]:
True

Solution 2: Sort and Compare

$nlog(n)$

In [23]:
def anagram2(s1, s2):
    alist1 = list(s1)
    alist2 = list(s2)
    
    alist1.sort()
    alist2.sort()
    
    pos = 0
    matches = True
    
    while pos < len(s1) and matches:
        if alist1[pos] == alist2[pos]:
            pos = pos + 1
        else:
            matches = False
            
    return matches
In [20]:
anagram1("python", "typhon")
Out[20]:
True
In [22]:
anagram1("python", "tyhonz")
Out[22]:
False

Solution 3: Brute Force

In [30]:
def anagram3(s1, s2):
    """
    corpus = list(s1)
    word = []
    word.append(corpus[0])
    del corpus[0]
    
    word.append(corpus[0])
    del corpus[0]
    
    word.append(corpus[0])
    del corpus[0]
    
    word.append(corpus[0])
    del corpus[0]
    
    word.append(corpus[0])
    del corpus[0]
    
    word.append(corpus[0])
    del corpus[0]
    
    print(corpus, word)
    """
    
    word = []
    for i in ['d', 'o', 'g']:
        for j in ['d', 'o', 'g']:
            for k in ['d', 'o', 'g']:
                word.append(i)
                word.append(j)
                word.append(k)
                
        print(word)
        word = []
In [31]:
anagram3("python", "tyhonx")
['d', 'd', 'd', 'd', 'd', 'o', 'd', 'd', 'g', 'd', 'o', 'd', 'd', 'o', 'o', 'd', 'o', 'g', 'd', 'g', 'd', 'd', 'g', 'o', 'd', 'g', 'g']
['o', 'd', 'd', 'o', 'd', 'o', 'o', 'd', 'g', 'o', 'o', 'd', 'o', 'o', 'o', 'o', 'o', 'g', 'o', 'g', 'd', 'o', 'g', 'o', 'o', 'g', 'g']
['g', 'd', 'd', 'g', 'd', 'o', 'g', 'd', 'g', 'g', 'o', 'd', 'g', 'o', 'o', 'g', 'o', 'g', 'g', 'g', 'd', 'g', 'g', 'o', 'g', 'g', 'g']

Solution 4: Count and Compare

In [ ]:
def anagram4(s1, s2):
    c1 = [0]*26
    c2 = [0]*26
    
    # Frequency Counting
    for i in range(len(s1)):
        pos = ord(s1[i]) - ord('a')
        c1[pos] += 1
        
    for i in range(len(s2)):
        pos = ord(s2[i]) - ord('a')
        c2[pos] += 1
        
    j = 0
    still_ok = True
    while j < 26 and still_ok:
        if c1[j] == c2[j]:
            j += 1
        else:
            still_ok = False
            
    # return c1 == c2
    
    return still_ok
In [33]:
[1,2,3,4] == [1,2,3,4]
Out[33]:
True