Anagrams Checker – 三种JavaScript解决方案

我开始了一系列关于常见算法和javascript问题的JavaScript解决方案。如果你错过了第一个，这里是它的链接。本周早些时候，我写了一篇关于Big O符号的文章。如果您不熟悉它，可能需要阅读它，因为本文中使用了一些概念。让我们直接回答问题陈述。

寻找字谜 – 问题

字谜是具有相同数量的相同字符的单词。这意味着如果我们可以重新安排一个字符串以获得另一个字符串，则两个字符串是字谜。

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

1. “听”和“沉默”
2. “铁路安全”和“童话故事”
3. “宿舍”和“肮脏的房间”
4. “眼睛”和“他们看到”

为了解决这个问题，我们假设如下：

1. 我们忽略了额外的字符，如“”，“@”等，以及空格。
2. 我们只想使用小写字符。

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

解决方案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个连续的forloops没有嵌套。忽略常数和其他因素，时间复杂度近似为线性，即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（n2）。

结论

我们已经看到了解决方案及其大致的时间复杂性。比较它们的时间复杂性，第一种解决方案似乎具有更好的性能。它具有O（n）的近似时间复杂度。然而，第二种解决方案更简洁。因此，您可以根据对您更重要的内容选择任何解决方案。

有任何问题或补充？请发表评论。

谢谢你的阅读。