字谜检查器 - 三种 JavaScript 解决方案

我发起了一系列关于常见算法和 JavaScript 问题的 JavaScript 解决方案。如果您错过了第一篇，可以点击这里查看。本周早些时候，我写了一篇关于大 O 符号的文章。如果您不熟悉大 O 符号，不妨读一读，因为本文会用到一些概念。现在我们直接进入问题描述。

寻找字谜——问题

字谜是指包含相同数量相同字符的单词。这意味着，如果我们可以重新排列一个字符串得到另一个字符串，那么这两个字符串就是字谜。

以下是一些字谜单词的例子。

“听”与“沉默”
“铁路安全”与“童话故事”
“宿舍”和“脏乱的房间”
“眼睛”和“它们看见”

为了解决这个问题，我们假设以下内容：

我们忽略“！”，“@”等多余的字符和空格。
我们只想使用小写字符。

让我们看看这个问题的一些解决方案。然后，我们将根据它们的时间复杂度进行比较。

解决方案 1 - 创建两个字符串的字符映射并比较映射

在此上下文中，字符映射是包含字符串中每个唯一字符的映射或对象。它将字符存储为键，并将其在字符串中出现的次数存储为值。

    function anagrams(stringA, stringB) {
        /*First, we remove any non-alphabet character using regex and convert
        convert the strings to lowercase. */
        stringA = stringA.replace(/[^\w]/g, "").toLowerCase()
        stringB = stringB.replace(/[^\w]/g, "").toLowerCase()

        //Get the character map of both strings
        const charMapA = getCharMap(stringA)
        const charMapB = getCharMap(stringB)

        /* Next, we loop through each character in the charMapA, 
        and check if it exists in charMapB and has the same value as
        in charMapA. If it does not, return false */
        for (let char in charMapA) {
            if (charMapA[char] !== charMapB[char]) {
                return false
            }
        }

        return true
    }

    function getCharMap(string) {
        // We define an empty object that will hold the key - value pairs.
        let charMap = {}

        /*We loop through each character in the string. if the character 
        already exists in the map, increase the value, otherwise add it 
        to the map with a value of 1 */
        for (let char of string) {
            charMap[char] = charMap[char] + 1 || 1
        }
        return charMap
    }

for 循环的运行时复杂度是线性的，即 O(n)。在本例中，有 3 个连续的 for 循环，且不嵌套。忽略常量和其他因素，时间复杂度近似为线性，即 O(n)。

2. 对字符串进行排序并检查它们是否相同

这是一种更简洁、更干净的检查两个字符串是否为字母重排的方法。
在本例中，我们将字符串转换为数组，使用 Array.sort()
方法对其进行排序，然后再将其转换回字符串。然后，我们比较两个字符串，检查它们是否相同。

    function anagrams(stringA, stringB) {
        /*First, we remove any non-alphabet character using regex and convert       
        convert the strings to lowercase. */
        stringA = stringA.replace(/[^\w]/g, '').toLowerCase()
        stringB = stringB.replace(/[^\w]/g, '').toLowerCase()

        return sortString(stringA) === sortString(stringB)
    }

    /*This function sorts the strings*/ 
    function sortString(string) {
        return string.split('').sort().join('');
    }

Array.sort 使用合并排序，因此其时间复杂度为 O(nlogn)。

3. 使用 Array.splice()

这又是一个解决方案。在本例中，我们将字符串 B 转换为一个数组，循环遍历字符串 A 中的每个字符，并检查它是否存在于字符串 B 的数组中。arrB如果存在，我们使用 Splice 方法将其从数组中删除。这样做是为了arrB避免重复检查出现多次的字符。

    function anagrams(stringA, stringB) {
        /*First, we remove any non-alphabet character using regex and convert       
        convert the strings to lowercase. */
        stringA = stringA.replace(/[^\w]/g, '').toLowerCase()
        stringB = stringB.replace(/[^\w]/g, '').toLowerCase()

        /*Next, we check if the lengths of the strings are equal. 
        If they are anagrams, they will have the same length. */
        if (stringA.length !== stringB.length) {
            return false
        }

        let arrB = stringB.split("")

        for (let char of stringA ){ 
            if (!arrB.includes(char)) {
                return false
                break;
            } else {
                arrB.splice(arrB.indexOf(char), 1)
            }
        }

        return true

    }

那么我们来考虑一下这个解决方案的时间复杂度。本例中，有三个循环运行：循环for、includes循环和splice循环。由于splice循环和循环之间includes没有嵌套，时间复杂度趋向于 O(n^2)。

结论

我们已经了解了这些解决方案及其大致的时间复杂度。比较它们的时间复杂度，第一个解决方案似乎性能更佳。它的时间复杂度近似为 O(n)。然而，第二个解决方案更简洁。因此，您可以根据自己的实际情况选择任何解决方案。

有任何问题或补充？请留言。

感谢您的阅读。

鏂囩珷鏉ユ簮锛�https://dev.to/sarah_chima/anagrams-checker- Three-javascript-solutions-53kp