1
\$\begingroup\$

Problem

Write a function to check whether two given strings are anagram of each other or not. An anagram of a string is a string that contains same characters ([A-Za-z0-9]) and the order of characters can be different.

Code

I've solved the anagram problem using a few methods with Python and JavaScript. If you'd like to review the codes and provide any change/improvement recommendations please do so, and I'd really appreciate that.

Python

import re


def are_anagram_naive_three(string_one: str, string_two: str) -> bool:
    """
    Returns True if two strings are anagram
    """
    return prep_input_strings_for_naive_three(string_one) == prep_input_strings_for_naive_three(string_two)


def are_anagram_naive_two(string_one: str, string_two: str) -> bool:
    """
    Returns True if two strings are anagram
    """
    return prep_input_strings_for_naive_two(string_one) == prep_input_strings_for_naive_two(string_two)


def prep_input_strings_for_naive_three(string: str) -> bool:
    """
    Prepares the input string using sorted, re.sub and lower methods
    """
    return sorted(replace_non_letters_digits(string.lower()))


def prep_input_strings_for_naive_two(string: str) -> dict:
    """
    Prepares the input string using a hashmap, re.sub and lower methods
    """
    return generate_hashmap(replace_non_letters_digits(string_one.lower()))


def generate_hashmap(string: str) -> dict:
    """
    Generates a hashmap: Keys are [A-Za-z0-9] and Values are the number of times those repeated
    """
    hashmap_char_counter = {}

    for char in string:
        try:
            hashmap_char_counter[char] = hashmap_char_counter[char] + 1
        except KeyError:
            hashmap_char_counter[char] = 1

    return hashmap_char_counter


def replace_non_letters_digits(string: str) -> str:
    """
    Re-subs non letters and digits of an input string
    """
    return re.sub(r'(?i)[^a-z0-9]+', '', string)


def are_anagram_naive_one(string_one: str, string_two: str) -> bool:
    """
    Returns boolean if two hashmaps of two cleaned strings are equal
    """
    string_one = re.sub(r'(?i)[^a-z0-9]+', "", string_one)
    string_two = re.sub(r'(?i)[^a-z0-9]+', "", string_two)
    hashmap_two, hashmap_two = {}, {}
    for letter in string_one.lower():
        if letter in hashmap_two.keys():
            hashmap_two[letter] += 1
        else:
            hashmap_two[letter] = 1

    for letter in string_two.lower():
        if letter in hashmap_two.keys():
            hashmap_two[letter] += 1
        else:
            hashmap_two[letter] = 1

    return hashmap_two == hashmap_two


if __name__ == '__main__':
    # ---------------------------- TEST ---------------------------
    DIVIDER_DASH_LINE = '-' * 50
    GREEN_APPLE = '\U0001F34F'

    strings_one = ["fairy tales", "eat for BSE", "bad credit", "he bugs Gore", "I’m a jerk but listen", "monkeys write", "rich-chosen goofy cult", "Uncle Sam's standard rot", "vile", "enraged", "tap", "elegant man",
                   "twelve plus one", "obecalp", "fluster", "real fun", "true lady", "store scum", "over fifty", "I am a weakish speller", "Radium came", "He bugs Gore", "I’m a jerk but listen", "I am Lord Voldemort"]
    strings_two = ["rail safety", "roast beef", "debit card", "George Bush", "Justin Timberlake", "New York Times", "Church of Scientology", "McDonald's restaurants", "evil", "angered", "pat",
                   "a gentleman", "eleven plus two", "placebo", "restful", "funeral", "adultery", "customers", "forty five", "William Shakespeare", "Madam Curie", "George Bush", "Tom Marvolo Riddle"]

    for string_one in strings_one:
        for string_two in strings_two:
            if are_anagram_naive_one(string_one, string_two) is True and are_anagram_naive_two(string_one, string_two) is True and are_anagram_naive_three(string_one, string_two) is True:
                print(DIVIDER_DASH_LINE)
                print(f'{GREEN_APPLE} "{string_one}" and "{string_two}" are anagram.')
                break

Output

--------------------------------------------------
🍏 "fairy tales" and "rail safety" are anagram.
--------------------------------------------------
🍏 "eat for BSE" and "roast beef" are anagram.
--------------------------------------------------
🍏 "bad credit" and "debit card" are anagram.
--------------------------------------------------
🍏 "he bugs Gore" and "George Bush" are anagram.
--------------------------------------------------
🍏 "I’m a jerk but listen" and "Justin Timberlake" are anagram.
--------------------------------------------------
🍏 "monkeys write" and "New York Times" are anagram.
--------------------------------------------------
🍏 "rich-chosen goofy cult" and "Church of Scientology" are anagram.
--------------------------------------------------
🍏 "Uncle Sam's standard rot" and "McDonald's restaurants" are anagram.
--------------------------------------------------
🍏 "vile" and "evil" are anagram.
--------------------------------------------------
🍏 "enraged" and "angered" are anagram.
--------------------------------------------------
🍏 "tap" and "pat" are anagram.
--------------------------------------------------
🍏 "elegant man" and "a gentleman" are anagram.
--------------------------------------------------
🍏 "twelve plus one" and "eleven plus two" are anagram.
--------------------------------------------------
🍏 "obecalp" and "placebo" are anagram.
--------------------------------------------------
🍏 "fluster" and "restful" are anagram.
--------------------------------------------------
🍏 "real fun" and "funeral" are anagram.
--------------------------------------------------
🍏 "true lady" and "adultery" are anagram.
--------------------------------------------------
🍏 "store scum" and "customers" are anagram.
--------------------------------------------------
🍏 "over fifty" and "forty five" are anagram.
--------------------------------------------------
🍏 "I am a weakish speller" and "William Shakespeare" are anagram.
--------------------------------------------------
🍏 "Radium came" and "Madam Curie" are anagram.
--------------------------------------------------
🍏 "He bugs Gore" and "George Bush" are anagram.
--------------------------------------------------
🍏 "I’m a jerk but listen" and "Justin Timberlake" are anagram.
--------------------------------------------------
🍏 "I am Lord Voldemort" and "Tom Marvolo Riddle" are anagram.

JavaScript

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

function are_anagram_sort_join(string_one, string_two) {
    string_one = replace_non_letters_digits(string_one);
    string_two = replace_non_letters_digits(string_two);

    if (string_one.split('').sort().join('') === string_two.split('').sort().join('')) {
        return true;
    }

    return false;
}


function are_anagram_sort_stringify(string_one, string_two) {
    string_one = replace_non_letters_digits(string_one);
    string_two = replace_non_letters_digits(string_two);

    if (JSON.stringify(string_one.split('').sort()) === JSON.stringify(string_two.split('').sort())) {
        return true;
    }

    return false;
}

function are_anagram_naive(string_one, string_two) {
    string_one = replace_non_letters_digits(string_one);
    string_two = replace_non_letters_digits(string_two);

    if (string_one.length != string_two.length) {
        return false;
    }

    const string_one_hashmap = generate_hashmap(string_one);
    const string_two_hashmap = generate_hashmap(string_two);

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

    return true;
}

function generate_hashmap(input_str) {
    hashmap_char_counter = {};

    for (let char of input_str) {
        hashmap_char_counter[char] = hashmap_char_counter[char] + 1 || 1;
    }
    return hashmap_char_counter;
}

function replace_non_letters_digits(str) {
    return str.replace(/[^a-z0-9]/gi, '');
}


strings_one = ["fairy tales", "eat for BSE", "bad credit", "he bugs Gore", "I’m a jerk but listen", "monkeys write", "rich-chosen goofy cult", "Uncle Sam's standard rot", "vile", "enraged", "tap", "elegant man", "twelve plus one", "obecalp", "fluster", "real fun", "true lady", "store scum", "over fifty", "I am a weakish speller", "Radium came", "He bugs Gore", "I’m a jerk but listen", "I am Lord Voldemort"];
strings_two = ["rail safety", "roast beef", "debit card", "George Bush", "Justin Timberlake", "New York Times", "Church of Scientology", "McDonald's restaurants", "evil", "angered", "pat", "a gentleman", "eleven plus two", "placebo", "restful", "funeral", "adultery", "customers", "forty five", "William Shakespeare", "Madam Curie", "George Bush", "Tom Marvolo Riddle"];

for (let string_one of strings_one) {
    for (let string_two of strings_two) {
        if (are_anagram_naive(string_one, string_two) && are_anagram_sort_stringify(string_one, string_two) && are_anagram_sort_join(string_one, string_two)) {
            console.log('🍏 "'.concat(string_one, '" and "', string_two, '" are anagrams!'));
        }

    }
}

Source

\$\endgroup\$

1 Answer 1

Reset to default
1
\$\begingroup\$

Generate Hashmap

There is a data structure that's well optimized for this task: collections.Counter. It will take any iterable and generate a dictionary with keys being elements of your iterable and values are the number of occurrences:

from collections import Counter

x, y = 'fairy tales', 'rail safety'
c1, c2 = Counter(x), Counter(y)

c1
Counter({'a': 2, 'f': 1, 'i': 1, 'r': 1, 'y': 1, ' ': 1, 't': 1, 'l': 1, 'e': 1, 's': 1})

And they also do equivalence testing:

c1 == c2
True

Filtering strings

This could be done in a generator expression using the str.isalnum function, removing the need for regex:

from typing import Iterator

def clean_string(s: str) -> Iterator[str]:
    """
    yields lowercased strings that are alphanumeric characters
    only
    """
    yield from (c for c in s.lower() if c.isalnum())

Which can directly be consumed by Counter

from collections import Counter

x, y = "I’m a jerk but listen", "Justin Timberlake"

c1, c2 = Counter(clean_string(x)), Counter(clean_string(y))

c1 == c2

True

Alternatively, you can use the builtin filter and return that, which Counter can also consume:

def clean_string(s: str) -> Iterable[str]:
    """
    returns a filter object which yields only 
    alphanumeric characters from a string
    """
    return filter(str.isalnum, s.lower())

Fitting this into your __main__ loop with a function to check string1 against string2:

def is_anagram(s1: str, s2: str) -> bool:
    """
    returns a boolean based on equivalence-testing the Counters
    of two strings. The strings are filtered to only include alphanumeric
    characters
    """
    return Counter(clean_string(s1)) == Counter(clean_string(s2))

if __name__ == "__main__":
    ~snip~
    for string1 in strings_one:
        for string_two in strings_two:
            anagram = is_anagram(string1, string2)

            if anagram:
                # print things here
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.