# [Challenge] Anagram Detector

Here is it. It transforms both string in decimal sums and compares them. If sums are equal, then is an anagram.

https://repl.it/H55J/15

Looks like mtf was first with the list.pop idea, submitting my own version anyway:

``````def isanagramf(s1, s2):
IGN=" .,!?"
A=[i for i in s1 if i not in IGN]
for i in s2:
if i in IGN: pass
elif i in A: A.pop(A.index(i))
else: return 0
return 1 if len(A)==0 else 0
``````

Again, as the challenge description refers to wikipedia’s definition of anagram where spaces can spawn or disappear into thin air (which is counterintuitive to me), I use IGN string for such magic characters. They will be ignored when comparing the strings from input.

The algorithm builds A list out of first input string minus the magic chars, then pop 's each element found in the other string. If the strings are anagrams, list A will have been emptied by the end of the iteration.

Time complexity is O(m+n) without any overhead this time (m to build list A, n to iterate over string s2) but memory consumption depends on the input string length rather than the size of alphabet input strings can be built of. For comparing whole books, I’d use my previous code instead

1 Like

Using Scheme this time.
Refractoring & Improving, should be O(x), where x = max(n,m) = length of the longer string.
Should be very efficient to implement in C language.

1. Avoid using function such as string2->contains() and string->pop, it is likely very expensive.
2. Avoid converting string to list or vector to avoid unnecessary data copy
3. Create one vector of size 26, initialize to all 0. Represent number of occurrence for each character A-Z
4. Implement 2 Loop, this is to remove unnecessary if statement in each loop.
5. 1st loop iterate from 0 to Length of the shorter String, in each iteration, each character in shorter string increment the correspond vector item by 1. The longer string decrements the correspond vector item by 1
6. 2nd loop iterate from Length of the shorter String to length of longer string, each character in the longer string decrements the correspond vector item by 1
7. compare the resulting vector (of size 26) to another vector of size 26 with all 0 value, and return 0 or 1.
``````(define (checkAnagram shortStr longStr)
(define shortLen (string-length shortStr))
(define longLen  (string-length longStr))
(define shortChar 0)
(define longChar  0)

(define vecOut (make-vector 26 0))

(do
([i 0 (+ i 1)])
([= i shortLen])
(set! shortChar (- (char->integer (string-ref shortStr i)) 65))
(set! longChar  (- (char->integer (string-ref longStr i))  65))
(and (>= shortChar 0) (< shortChar 26 ) (vector-set! vecOut shortChar (+ (vector-ref vecOut shortChar) 1)))
(and (>= longChar 0)  (< longChar 26 )  (vector-set! vecOut longChar  (- (vector-ref vecOut longChar)  1)))
)

(do
([i shortLen (+ i 1)])
([= i longLen])
(set! longChar  (- (char->integer (string-ref longStr i))  65))
(and (>= longChar 0)  (< longChar 26 )  (vector-set! vecOut longChar  (- (vector-ref vecOut longChar)  1)))
)

(if (equal? vecOut (make-vector 26 0))
1
0
)
)

(define (anagram strA strB)
(if (< (string-length strA) (string-length strB))
(checkAnagram strA strB)
(checkAnagram strB strA)
)
)

(print (anagram "ABC ABC" "B A C    C     A       B"))
(print (anagram "ABC" "DEF"))
(print (anagram "AB          C" "B  AC"))
(print (anagram "AB          C" "DEF"))
``````

https://repl.it/Hdms/0

Python 2:

``````def anagram_tester(x, y):
x2 = set(x)
y2 = set(y)
if len(x2) == len(y2) and x2 & y2 == x2:
return("%s and %s are anagrams." %(x,y))
else:
return("%s and %s are not anagrams." %(x,y))
``````
3 Likes

I am in love with your code

1 Like

On to feedback and “winners,” with special thanks to our crack team of @moderateurs (especially @alexcraig and @factoradic)!

##The Winners

@tomegz (Tomek) - nice use of a map, makes it less space efficient, but a very nice JavaScript approach. Solution deals with spaces, breaks if `occur < 0`. Other than the code being a wee bit (arguably) messy, this was a near-flawless method.
See Tomek’s entry and explanation.

## @cloudrunner15916 (David Springer) - We really liked this Python solution, all done in one array (so more efficient), and nice use of `any()`. In the second loop, we would check if the value is `< 0`, in some cases this would result in much faster execution.See David’s entry and explanation.

##Honorable mentions:

@devour30 - good approach, chosen lower case letters instead of upper case, doesn’t work with spaces

@javiervfa - interesting approach, runs in correct `O(n+m)` time (just), novel way of counting each letter, not quite as efficient as other methods

@cdipietro11 - nice solution with lots of error handling, and a nice menu (possibly over-engineered but we like it), runs in correct time, but fails with spaces unfortunately

@ajaxninja40882 - We thought your C++ solution was very nice, similar counting letters approach to some others, making sure they are equal in the two strings, deals with spaces. You decided to allocate some memory in the beginning for the faster execution, and this is something we would do too, especially when the alphabet is so limited! Your solution uses a single array for storing character occurrences… all in all very good code. In the second loop, we would check if the value is `< 0`, in some cases this would result in much faster execution. Thank you for posting in C++, even though we don’t teach C++ at Codecademy and so this is ineligible to win, we really like the variety.

@netmaster34973 - Very good Python approach! Very close to what we would call a flawless solution. The problem is… you made a simple mistake that you must have overlooked. You use a list of length `23`, but there are `26` characters, so you will get an index out of range error if input includes `Z`, for example. Furthermore your solution lacks support for spaces. Unfortunately this mistakes keep you from winning, but we did want to say that your approach was fantastic.

@appsco2012_dasancor8 - nice java implementation, but using the numerical value doesn’t work. E.g. “AD” and “BC” have the same value but are not anagrams

Thanks again! See May 3rd’s challenge here.

3 Likes

//The solution accepts lowercase and uppercase ASCII characters and spaces

//Identify first character from 1st string and remove all its occurrences from both strings
//This is done for as long as both strings have the same length and 1st string is not empty

//If in result of the above the length of 1st string is different from the length of 2nd string then
//either the strings had a different length from beginning (excluding spaces) or one string had more instances of a character then another
//In both cases the 2nd string is not an anagram of 1st string

https://repl.it/HetY/3

1 Like

Good work! you are really good in python.

Not half so good as the other entries. I work at it. What results is anyone’s guess.

2 Likes

Thank you very much.

``````class anagram{
static void check(String first, String second){
int flag=1;
int check[]=new int[26];
int check1[]=new int[26];

for(int i=0; i<first.length(); i++)
if(first.charAt(i)!=' ')
check[first.charAt(i)-'A']++;

for(int i=0; i<second.length(); i++)
if(second.charAt(i)!=' ')
check1[second.charAt(i)-'A']++;

for(int i=0; i<check.length; i++){
if(check[i]!=check1[i])
flag=0;
}
if(flag==1)
System.out.println("anagram");
else
System.out.println("not anagram");
}
}
class main1{
public static void main(String...s){
anagram.check("TOM MARVOLO RIDDLE","I AM LORD VOLDEMORT");
}
}
``````

https://goo.gl/mZMlbY

Take two arrays of size of 26 memory blocks and initialize them with 0.
Convert Strings into character and subtract each character from ‘A’
after subtraction we get index number (for example: for A it will give us ‘A’-‘A’=0) on that index zero is stored already just increment that particular value after doing all character…

just compare parallely two arrays. If their values are same then Strings are anagram else they are not.

thank you! happy coding!

1 Like

Great job!
Keep up the good work…Good luck!

def anagramma(stringa1,stringa2):

#check if the lengh is the same for the strings, otherwise return 0

``````if len(stringa1) !=len(stringa2):
print(0)
return(0)
else:

#create an empty list and put zero if the single caracter of the first string is not in the second string.
lista=[]
for x in stringa1:
if x not in stringa2:
lista.append(0)
else:
lista.append(1)

#if there is at least one "0" in the list, the string is not the anagram of the other and we return 0; otherwise we return 1
if 0 in lista:
print(0)
return 0
else:
print(1)
return 1``````

Hey @cloudsolver39392, this is generally a nice solution idea, except it will not work with strings where second string has characters not present in 1st string, e.g. stringa1=“aa” stringa2=“ab”.

I have proposed a very similar solution which deals with the issue above and also decreases number of operations for longer strings by removing similar characters from both strings.

If you are interested, please check #54 from above.

Thank you
I will check it

https://repl.it/HsBf/4

I like this challenge so I thought I’d give my (quick and dirty) solution — using functional programming

process:
convert strings to one case,
convert strings to array (so I can use builtin Array.prototype.*),
map chars in array to: [char, number of matches for each char],
sort resultant array by char,
remove duplicate entries in occurrences array,
compare arrays’ chars and values.

Python 3, two different approaches. The first strips the strings of spaces, then compares a sorted list of each to see if equal. This seemed almost too easy, so I wrote a second function that does the stripping, then steps through the first string character by character as a list and pulls the first instance of that character from the second string (as a list) if there. If second string list is empty at the end, you have an anagram! I also had to add a length check for the second function, as a shorter second string could result in a false confirmation. Oh, and yes, I did discover that Python can strip spaces much more easily than I did it…

https://repl.it/IY6H/0

Python 3.6 -

``````def anagram_detector(first: str, second: str) -> int:
# Keep the count of each alphabet a...z in a dictionary
occurances = {}
count = 0
# Use lower case characters for ease and simplicity
for char in first.lower():
# Skip the characters that are not alphabets
if not char.isalpha(): continue
# keep count of alphabets in first string
count += 1
# Increase the count of each alphabet by 1, or initiate its count with 1 if not present in the dictionary
occurances[char] = occurances.get(char, 0) + 1
for char in second.lower():
if not char.isalpha(): continue
# keep count of alphabets in second string
count -= 1
# if count of current alphabet is already 0, that means it's new and not present already, or the alphabet's count is more in second string than first
if occurances.get(char, 0) == 0:
return 0
# Decrease the count of each alphabet by 1
occurances[char] -= 1
# if count is not equal to zero i.e. second string has more/less characters than first string, return 0
return int(count == 0)
``````

Last statement will convert True to 1 and False to 0.

I came up with this solution, which is similar to some of the previous entries, including winners.
But I think my solution is better because @tomegz and @cloudrunner15916 solutions loops over dictionary at last, which I find unnecessary. All the cases are handled in the for loop over second string.
Best time complexity is O(n) (in case, unknown alphabets from first string emerge at the start in second string) and worst time complexity is O(n + m), where n and m are usual lengths of both strings respectively.
The program works for all strings.

https://repl.it/Lgfs

1 Like

I’m very late to this challenge, but I think I wrote a Javascript solution that works. It should work for strings with capital letters and space characters, like the directions say. I didn’t try the intermediate challenge, just the basic challenge.

``````function anagramDetector(str1, str2) {

// Convert string 1 to an array of its characters and remove spaces:
arr1 = Array.from(str1);
while (arr1.includes(' ')) {
arr1.splice(arr1.indexOf(' '), 1);
}

// Convert string 2 to an array of its characters and remove spaces:
arr2 = Array.from(str2);
while (arr2.includes(' ')) {
arr2.splice(arr2.indexOf(' '), 1);
}

// Check if the two arrays are the same length; if not, the strings are not anagrams:
if (arr1.length !== arr2.length) {
return 0;
}

// Check each character in string 1. If it exists in string 2, then strike it from string 2's array. If it does not exist in string 2, then the strings are not anagrams:
for (char of arr1) {
if (arr2.includes(char)) {
arr2.splice(arr2.indexOf(char), 1);
} else {
return 0;
}
}

// If the function has not already returned a 0, then we were able to find every character from string 1 in string 2, and the two are anagrams:
return 1;
}
``````

Code on repl.it: https://repl.it/@JessicaAHom/03anagramDetector

Thanks for sharing great things related to the anagram code it helps me to complete my Anagram Generator project and also I learn new things in python while working on the project.