DEV Community

tommy-3
tommy-3

Posted on

Learning Algorithms with JS, Python and Java 7: Anagrams

This is the seventh article of my attempts to follow Stephen Grider's Udemy course in three different languages. JavaScript solutions are by Stephen. I try to "translate" it into Python and Java.

Today's question is:

Check to see if two provided strings are anagrams of eachother.
One string is an anagram of another if it uses the same characters
in the same quantity. Only consider characters, not spaces
or punctuation. Consider capital letters to be the same as lower case
--- Examples
anagrams('rail safety', 'fairy tales') --> True
anagrams('RAIL! SAFETY!', 'fairy tales') --> True
anagrams('Hi there', 'Bye there') --> False

1: Counting each letter

JavaScript:

function anagrams(stringA, stringB) {
  const charMapA = buildCharMap(stringA);
  const charMapB = buildCharMap(stringB);

  if (Object.keys(charMapA).length !== Object.keys(charMapB).length) {
    return false;
  }

  for (let char in charMapA) {
    if (charMapA[char] !== charMapB[char]) {
      return false;
    }
  }

  return true;
}

function buildCharMap(str) {
  const charMap = {};

  for (let char of str.replace(/[^\w]/g, '').toLowerCase()) {
    charMap[char] = charMap[char] + 1 || 1;
  }

  return charMap;
}
Enter fullscreen mode Exit fullscreen mode

Python:

import re
from collections import Counter

def anagrams(string_a: str, string_b: str) -> bool:
    char_map_a = build_counter(string_a)
    char_map_b = build_counter(string_b)

    if len(char_map_a.keys()) != len(char_map_b.keys()):
        return False

    for char in char_map_a.keys():
        if char not in char_map_b or char_map_a[char] != char_map_b[char]:
            return False

    return True

def build_counter(string: str) -> Counter:
    return Counter(re.sub(r'[^\w]', '', string, flags=re.UNICODE).lower())
Enter fullscreen mode Exit fullscreen mode

Actually this works, too:

import re
from collections import Counter

def anagrams(string_a: str, string_b: str) -> bool:
    return build_counter(string_a) == build_counter(string_b)

def build_counter(string: str) -> Counter:
    return Counter(re.sub(r'[^\w]', '', string, flags=re.UNICODE).lower())
Enter fullscreen mode Exit fullscreen mode

Java:

import java.util.Map;
import java.util.stream.Collectors;

public static boolean anagrams(String stringA, String stringB) {
    Map<Character, Long> charMapA = buildCharMap(stringA);
    Map<Character, Long> charMapB = buildCharMap(stringB);

    if (charMapA.keySet().size() != charMapB.keySet().size()) {
        return false;
    }

    for (char chr : charMapA.keySet()) {
        if (!charMapB.containsKey(chr) || !charMapA.get(chr).equals(charMapB.get(chr))) {
            return false;
        }
    }
    return true;
}

private static Map<Character, Long> buildCharMap(String str) {
    return str.replaceAll("[^\\w]", "")
            .toLowerCase()
            .chars()
            .mapToObj(i -> (char) i)
            .collect(Collectors.groupingBy(c -> c, Collectors.counting()));
}
Enter fullscreen mode Exit fullscreen mode

2: Sort to compare

JavaScript:

function anagrams(stringA, stringB) {
  return cleanString(stringA) === cleanString(stringB);
}

function cleanString(str) {
  return str
    .replace(/[^\w]/g, '')
    .toLowerCase()
    .split('')
    .sort()
    .join('');
}
Enter fullscreen mode Exit fullscreen mode

Python:

import re

def anagrams(string_a: str, string_b: str) -> bool:
    return clean_string(string_a) == clean_string(string_b)

def clean_string(string: str) -> str:
    lower = re.sub(r'[^\w]', '', string, flags=re.UNICODE).lower()
    return ''.join(sorted(lower))
Enter fullscreen mode Exit fullscreen mode

Java:

import java.util.stream.Collectors;

public static boolean anagrams(String stringA, String stringB) {
    return cleanString(stringA).equals(cleanString(stringB));
}

private static String cleanString(String str) {
    return str.replaceAll("[^\\w]", "")
            .toLowerCase()
            .chars()
            .mapToObj(i -> (char) i)
            .sorted()
            .map(String::valueOf)
            .collect(Collectors.joining());
}
Enter fullscreen mode Exit fullscreen mode

I hope you enjoyed this. I'd appreciate any comments and feedback.

Top comments (4)

Collapse
 
kepta profile image
Kushan Joshi • Edited

Great article Tommy!

I love finding smaller solutions to problems, here is a similar attempt to your question on anagrams.

function anagrams(a, b) {
  a = a.replace(/[^\w]/g, "").toLowerCase();
  b = b.replace(/[^\w]/g, "").toLowerCase();

  if (a.length !== b.length) return false;

  return [...a].sort().join() ===  [...b].sort().join()
}

Enter fullscreen mode Exit fullscreen mode
Collapse
 
kepta profile image
Kushan Joshi • Edited

This is a great solution Sam, the only thing I worry about is that multiplication though theoretically is an O(1) operation, but in for strings of size > 50, we will have resort to Big integers and multiplication there is not exactly O(1).

Also played a bit of code golf with your algorithm

const primeSum = word =>
  word
    .map(char => primes.get(char.toLowerCase()))
    .filter(char => char !== undefined)
    .reduce((prev, cur) => prev * cur);
Collapse
 
stevenbrown163 profile image
Steven Brown

Nice thing about this method, you can use modulus to check if a string is a substring of another (“apple” to “applesauce”).

Thread Thread
 
kepta profile image
Kushan Joshi

That might give false positive for jumbled words, for example paple would pass the modulous check.