# 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