在一次技术面试中我遇到了这个问题，但在给定的时间内失败了。之后，我坐下来解决了我认为是一个好的解决方案。实际上，我的任务是构建一个AngularJS应用程序来做到这一点，但是我的解决方案的核心是JavaScript。我想问一下是否有更好的方法可以做到这一点：

// convert strings to LC for case insensitivity
// split strings into arrays
// sort the arrays (spaces will sort first and be trimmed later)
// join the arrays back into strings
// we're only concerned about the printable characters in the anagram so,
// trim() to remove any spaces and then compare the resulting strings
var str1 = this.word1.toLowerCase().split('').sort().join('').trim();
var str2 = this.word2.toLowerCase().split('').sort().join('').trim();

if (str1 === str2) {
    this.isAnagram = true;
} else {
    this.isAnagram = false;
}


评论

通常，最好的解决方案在很大程度上取决于您的约束条件，这些约束条件尚不清楚。您可以假设word1和word2实际上都是字符串吗？您可以假设它们仅包含字母吗？您需要类型转换吗？您是否需要将“ÿ”视为“ y”？您是否需要错误处理？等等...
如果您要在团队中为真实项目编写真实代码，那么上面的解决方案是完美的。也就是说，软件20年以来唯一关心的问题就是可读性和清晰度-因此，您会获得A。这是一个有趣的，有历史意义的脚注，但是请注意，当然，如果您提出的“绩效”解决方案完全失败了：您的工作，生存，生活，心跳都是一个简单的概念：可读性。）
关于这一点，现在的质量检查非常混乱。我觉得值得重申一下（1）匹配一个字谜（排序，相等）是一个完全，完全，完全琐碎的过程（2），当然，显然，您是使用完全琐碎的.Net在一行代码中完成的为此可以使用的电话。简单地说，您将完全无法想象您将开始“编写代码”！要做到这一点。只不过您会开始“编写代码”！例如，将两个数字相除或将字符串变成小写。
很抱歉，经常使用“完全”一词，但这就是质量检查的类型！ :)
检查两个字符串是否为字谜的可能重复项

#1 楼

我最初的断言（过时）：


对字符串（或任何数组）进行排序效率低下，因为即使
最快的算法也不会比O（n log n）快平均
情况。最有效的方法是使用哈希图对每个单词中的字母计数。像这样：


尽管从哈希映射中读取数据的速度可以与O（1）一样快，但是写入哈希映射的速度明显较慢。通过使用26值数组（0-25）表示小写字母，可以大大提高运算速度：

function isAnagram(word1, word2) {
  if (typeof word1 !== 'string' || typeof word2 !== 'string') {
    throw new Error('isAnagram requires two strings to be passed.')
  }

  var normalizedWord1 = word1.replace(/[^A-Za-z]+/g, '').toLowerCase();
  var normalizedWord2 = word2.replace(/[^A-Za-z]+/g, '').toLowerCase();

  var counts = [];
  var word1Length = normalizedWord1.length;
  var word2Length = normalizedWord2.length

  if (word1Length !== word2Length) { return false; }

  for (var i = 0; i < word1Length; i++) {
    var index = normalizedWord1.charCodeAt(i)-97;
    counts[index] = (counts[index] || 0) + 1;
  }

  for (var i = 0; i < word2Length; i++) {
    var index = normalizedWord2.charCodeAt(i)-97;
    if (!counts[index]) { return false; }
    else { counts[index]--; }
  }

  return true;
}


编辑：使用哈希并使用26值数组：
http://jsperf.com/anagram-algorithms

评论

\ $ \ begingroup \ $
是的。 3n比n log n快一个数量级。
\ $ \ endgroup \ $
–罗兰
15年8月7日在4:13
\ $ \ begingroup \ $
@Tushar如果您对学习计算复杂性感兴趣，请访问：en.wikipedia.org/wiki/Big_O_notation
\ $ \ endgroup \ $
–罗兰
2015年8月7日在4:17
\ $ \ begingroup \ $
@EasyBB是的，我不知道..in慢得多。快速的Google搜索启发了我。谢谢！
\ $ \ endgroup \ $
–罗兰
15年8月7日在5:08
\ $ \ begingroup \ $
-1因为HashMap通常实现为Heap，所以用于插入的O（log n）。更重要的是。您实际上是在对堆进行插入排序，“ dun dun dun”为O（n log n）。
\ $ \ endgroup \ $
–阿伦
15年8月7日在6:37
\ $ \ begingroup \ $
@Aron您对插入速度很满意。我通过将小写字符转换为值0-25来加速算法，以便可以通过数组索引而不是哈希键快速查找它们。
\ $ \ endgroup \ $
–罗兰
15年8月7日在7:12

#2 楼

每个人都在谈论您的算法，但是每个人都会犯同样的错误。

重复的代码！是的，您重复了代码。

请看以下几行：并反复！将其移至新功能：

var str1 = this.word1.toLowerCase().split('').sort().join('').trim();
var str2 = this.word2.toLowerCase().split('').sort().join('').trim();


现在您可以执行以下操作：

var regularize = function(str) {
    return str.toLowerCase().split('').sort().join('').trim();
}


但是您可以在下面找到以下几行代码： > 
var str1 = regularize(this.word1);
var str2 = regularize(this.word2);



如前所述，您可以对字符串进行一些清理。正则表达式浮现在我的脑海。根据@Tushar的回答，我想到了：

if (str1 === str2) {
    this.isAnagram = true;
} else {
    this.isAnagram = false;
}



所有组件组装在一起：
很短，不是吗？

评论

\ $ \ begingroup \ $
请给我解释下票的好意
\ $ \ endgroup \ $
–伊斯梅尔·米格尔（Ismael Miguel）
15年8月10日在8:02
\ $ \ begingroup \ $
尽管我喜欢某个人专注于可读性，但我认为将两倍代码的这一部分移到一个单独的函数中并不会增强可读性-而是需要在其他地方引用以查看代码的作用。当代码简单地在连续的行上重复时，很明显代码是相同的。 （尽管不是我的选票。）
\ $ \ endgroup \ $
– Brilliand
15年8月10日在21:16
\ $ \ begingroup \ $
@Brilliand这个想法是为了提高可读性，以使代码DRY并减少其他问题。两种方式仍然存在相同的惯用意思。我的只是消除了所有膨胀。我相信比起原始版本更容易阅读。是的，您必须引用其他位置，但是如果重复某些操作，也许是时候使用它自己的功能了。
\ $ \ endgroup \ $
–伊斯梅尔·米格尔（Ismael Miguel）
15年8月11日在8:39
\ $ \ begingroup \ $
将重复的代码移入其自身的功能是改进其实现的先决条件（例如，我们可以填充直方图）。如果在重构函数之后，您认为值得再次内联，那是在此时做出的决定。因此，我全都愿意像这样提取重复的功能-非常有帮助。
\ $ \ endgroup \ $
– Toby Speight
18年8月23日在10:08

#3 楼

您的解决方案是在检查两个字符串是否为Anagram之前不删除标点符号和空格。

还可以优化代码。


首先，删除所有空格使用正则表达式从两个字符串中删除和标点符号

检查字符串length是否相等，如果不相等则立即返回false
仅当两个字符串长度相等时才检查Anagram。 />
代码：

var regex = /[^a-z0-9]/gi;

var str1 = this.word1.replace(regex, ''),
    str2 = this.word2.replace(regex, '');

this.isAnagram = str1.length > 0 && str1.length === str2.length && (str1.toLowerCase().split('').sort().join('') === str2.toLowerCase().split('').sort().join(''));


首先将检查字符串length是否相等，如果相等，则仅评估(str1.toLowerCase().split('').sort().join('') === str2.toLowerCase().split('').sort().join(''))。

Regex解释



/：regex的分隔符


[]：字符类

[^..]：不包含以下任何字符

a-z0-9：所有字母数字字符

g：全局标志。匹配类中的所有字符

i：不区分大小写的匹配

Demo 




 var regex = /[^a-z0-9]/gi;
document.getElementById('btn').addEventListener('click', function() {

  var str1 = (document.getElementById('str1').value).replace(regex, ''),
    str2 = (document.getElementById('str2').value).replace(regex, '');

  var isAnagram = str1.length > 0 && str1.length === str2.length && (str1.toLowerCase().split('').sort().join('') === str2.toLowerCase().split('').sort().join(''));

  alert('Is Anagram: ' + isAnagram);
}, false); 

 <input type="text" id="str1" />
<br />
<input type="text" id="str2" />
<br />
<input type="button" id="btn" value="check" />





编辑

其他方法：

var checkAnagram = (function () {
    var sanitizeRegex = /[^a-z0-9]/gi;

    var sanitizeString = function (str) {
        return str.replace(sanitizeRegex, '').toLowerCase().split('').sort().join('');
    };

    return function (str1, str2) {
        return sanitizeString(str1) === sanitizeString(str2);
    };
}());

var isAnagram = checkAnagram('Rust! Ha?', 'Tushar'); // Usage


演示

评论

\ $ \ begingroup \ $
“ Rust Ha”被认为是“ Tushar”的字谜吗？如果是这样，那么这种方法将无法快速涵盖所有情况。
\ $ \ endgroup \ $
–詹森·斯珀斯凯（Jason Sperske）
15年8月7日，下午3:43
\ $ \ begingroup \ $
.toLowerCase（）。split（''）。sort（）的副作用之一是将所有空格排序到末尾（或开始，我没有测试哪个），但是这将使长度测试失败（尽管会进行修整）（花了我一段时间想出一个巧妙的七巧板来说明这一点，请不要冒犯:)
\ $ \ endgroup \ $
–詹森·斯珀斯凯（Jason Sperske）
2015年8月7日，下午3:47
\ $ \ begingroup \ $
@JasonSperske知道了。谢谢。我已经更新了答案
\ $ \ endgroup \ $
–图沙
2015年8月7日，下午3:54
\ $ \ begingroup \ $
如果我正在面试某人并寻找他们尝试解决编程难题的能力，我会认为这是一个很好的答案。锈？哈！ Tushar :)
\ $ \ endgroup \ $
–詹森·斯珀斯凯（Jason Sperske）
2015年8月7日，下午3:56
\ $ \ begingroup \ $
Downvoter，请在这里评论，为什么要投票？有什么可以改善的吗？
\ $ \ endgroup \ $
–图沙
15年8月7日在4:04

#4 楼

我有一些类似于Rrowland的样板代码，但我觉得我的算法可能会快一点。它通过使用质数乘法在O（n）中进行操作来对字母进行计数，并且在最长的例程中是非分支的。

我没有在数组ind - 97中保留97个空白点

我认为，如果您更痴迷，可以使用按位运算来进行计数，但这已经足够了。 br />编辑1

我想我们现在有一个速度竞赛，而且这个版本比所有先例（基准）要快得多。

function isAnagram(word1, word2) {
  if (!word1 || !word2 || !word1.length || !word2.length) {
    throw new Error('isAnagram requires two strings to be passed.')
  }

  var nword1 = word1.replace(/\s+/g, '').toLowerCase();
  var nword2 = word2.replace(/\s+/g, '').toLowerCase();

  var length1 = nword1.length;
  var length2 = nword2.length;

  if (length1 !== length2) {
    return false;
  }

  var word1hash = 1;
  var word2hash = 1;

  var primes = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101];

  var ind;
  for (var i = 0; i < length1; i++) {
    ind = nword1.charCodeAt(i);
    word1hash *= primes[ind];
  }

  for (var i = 0; i < length2; i++) {
    ind = nword2.charCodeAt(i);
    word2hash *= primes[ind];
  }

  console.log(word1hash);
  console.log(word2hash);

  return word1hash == word2hash;
}



编辑2

我知道这很傻，但是添加质数的对数实际上要快一点。 （基准）

function isAnagram(word1, word2) {
  if (!word1 || !word2 || !word1.length || !word2.length) {
    throw new Error('isAnagram requires two strings to be passed.')
  }

  var nword1 = word1;
  var nword2 = word2;

  var length1 = nword1.length;
  var length2 = nword2.length;

  if (length1 !== length2) {
    return false;
  }

  var word1hash = 1;
  var word2hash = 1;

  var tab = {'q': 2, 'w': 3, 'e': 5, 'r': 7, 't': 11, 'y': 13, 'u': 17, 'i': 19, 'o': 23, 'p': 29, 'a': 31, 's': 37, 'd': 41, 'f': 43, 'g': 47, 'h': 53, 'j': 59, 'k': 61, 'l': 67, 'z': 71, 'x': 73, 'c': 79, 'v': 83, 'b': 89, 'n': 97, 'm': 101, 'Q': 2, 'W': 3, 'E': 5, 'R': 7, 'T': 11, 'Y': 13, 'U': 17, 'I': 19, 'O': 23, 'P': 29, 'A': 31, 'S': 37, 'D': 41, 'F': 43, 'G': 47, 'H': 53, 'J': 59, 'K': 61, 'L': 67, 'Z': 71, 'X': 73, 'C': 79, 'V': 83, 'B': 89, 'N': 97, 'M': 101, ' ': 1}

  for (var i = 0; i < length1; i++) {
    word1hash *= tab[word1[i]]
  }

  for (var i = 0; i < length2; i++) {
    word2hash *= tab[word2[i]]
  }

  return word1hash == word2hash;
}


编辑3：删除了等长检查。

评论

\ $ \ begingroup \ $
+1素数乘法使其速度更快。不过，我可能会找到一种方法，将97个连续零的字面构造转换为更具可读性和可维护性的内容。
\ $ \ endgroup \ $
–罗兰
15年8月7日在18:44
\ $ \ begingroup \ $
@rrowland，我实际上不能确切确定字面量97零是否比从索引中减去97快。这只是一个推测。有趣的是，在jsperf上，当我在初始化程序的作用域中声明了质数时，整个函数变慢了—如图所示。
\ $ \ endgroup \ $
–西蒙·匡（Simon Kuang）
2015年8月7日在18:55


\ $ \ begingroup \ $
我运行了一个基准-rrowland的答案运行时间大约是OP的一半，这大约是rrowland的答案运行时间的一半。 （警告其他人进行基准测试或使用它：在运行一万次之前，请先删除console.logs。）
\ $ \ endgroup \ $
– Brilliand
15年8月7日在19:51
\ $ \ begingroup \ $
这是jsperf的比较：jsperf.com/anagram-algorithms/3
\ $ \ endgroup \ $
–罗兰
15年8月7日在19:56
\ $ \ begingroup \ $
我怀疑在某些长单词的情况下，如果不是，那么此函数将算作字谜，但是-javascript整数在某一点后开始失去精度，并且该函数趋于在十点后超过该阈值字母左右。
\ $ \ endgroup \ $
– Brilliand
2015年8月7日19:57


#5 楼

我有一个简单的例子

function isAnagram(strFirst, strSecond) {

 if(strFirst.length != strSecond.length)
       return false;

 var tempString1 = strFirst.toLowerCase();
 var tempString2 = strSecond.toLowerCase();

 var matched = true ;
 var cnt = 0;
 while(tempString1.length){
    if(tempString2.length < 1)
        break;
    if(tempString2.indexOf(tempString1[cnt]) > -1 )
        tempString2 = tempString2.replace(tempString1[cnt],'');
    else
        return false;

    cnt++;
 }

 return matched ;

 }


调用函数将是isAnagram("Army",Mary);
函数将返回true或false

评论

\ $ \ begingroup \ $
如果您解释了为什么此代码比OP和其他人发布的代码更好以及它与其他答案有何不同，这将有所帮助。
\ $ \ endgroup \ $
–地狱
16 Dec 8'在14:58