Anagram (Python，JavaScript)

Question

问题

编写一个函数来检查两个给定的字符串是否彼此相联。字符串的字元是包含相同字符(A-Za-z0-9)的字符串，字符的顺序可以是不同的。

码

我用Python和JavaScript的几种方法解决了字谜问题。如果您想检查代码并提供任何更改/改进建议，请这样做，我非常感谢。

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

输出

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

    }
}

源

• 检查两个字符串是否是彼此的对白？？极客表示极客。
• 阿格拉姆-维基

Answer 1

生成哈希映射

有一个数据结构对此任务进行了很好的优化：collections.Counter。它将使用任何可迭代的方法并生成一个字典，其中键是可迭代的元素，值是出现的次数：

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

他们还做等值测试：

c1 == c2
True

过滤字符串

这可以使用str.isalnum函数在生成器表达式中完成，从而消除了正则表达式的需要：

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

它可以被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

或者，您可以使用内置的filter并返回它，Counter也可以使用它：

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

在您的__main__循环中使用一个函数来检查string1和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