Learning Algorithms with JS, Python and Java 7: Anagrams

#beginners #javascript #python #java

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;
}

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())

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())

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()));
}

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('');
}

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))

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());
}

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

Top comments (4)

Kushan Joshi • Aug 29 '18 • 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()
}

Kushan Joshi • Aug 29 '18 • 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);