Определение того, являются ли два слова анаграммами

Мне была дана эта проблема в техническом интервью и яростно потерпел неудачу в указанное время. Впоследствии я сел и разработал то, что я считаю хорошим решением. Задача состояла в том, чтобы создать приложение 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;
}
36 голосов | спросил Lazloman 7 AM00000060000004231 2015, 06:16:42

5 ответов


26

Мое первоначальное утверждение (устаревшее):

  

Сортировка строки (или любого массива) неэффективна, поскольку даже   самый быстрый алгоритм будет сортировать не быстрее, чем 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;
}

EDIT: сравнение скорости между использованием хэша и использованием массива с 26 значениями: http://jsperf.com/anagram-algorithms

ответил rrowland 7 AM00000060000003631 2015, 06:50:36
20

Все говорят о вашем алгоритме, но каждый делает ту же ошибку.

Повторный код! Да, у вас есть повторный код.

Посмотрите на следующие строки:

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

Но у вас есть несколько строк ниже:

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

Итак, вам не нужны эти переменные или что-то еще ... Очистка, вы можете просто сделать:

this.isAnagram = regularize(this.word1) == regularize(this.word2);

Как было предложено много раз раньше, вы можете выполнить некоторую очистку строки. Регулярные выражения приходят мне в голову. Основываясь на ответе @ Тушара , я придумал следующее:

var regularize = function(str) {
    return str.toLowerCase().replace(/[^a-z\d]/g,'').split('').sort().join('');
}

Все собраны вместе:

var regularize = function(str) {
    return str.toLowerCase().replace(/[^a-z\d]/g,'').split('').sort().join('');
}
this.isAnagram = regularize(this.word1) == regularize(this.word2);

Довольно короткий, не так ли?

ответил Ismael Miguel 7 PM000000120000004331 2015, 12:23:43
7

Ваше решение не удаляет пунктуации и пробелы , прежде чем проверять, являются ли две строки Anagrams .

Кроме того, код может быть оптимизирован.

  1. Во-первых, удалите все пробелы и знаки препинания из обеих строк, используя Regular Expression
  2. Убедитесь, что строки length равны , если не вернуть false
  3. Проверьте Anagrams только тогда, когда обе строки имеют одинаковую длину.

код:

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 Explanation

  1. /: разделитель regex
  2. []: класс символов
  3. [^..]: Не , содержащий любой из следующих символов
  4. a-z0-9: все буквенно-цифровые символы
  5. g: глобальный флаг. Соответствует всем символам класса
  6. i: нечувствительность к регистру

Демо

 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" />

Edit

Другой подход:

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

Демо

ответил Tushar 7 AM00000060000000231 2015, 06:36:02
3

У меня есть код шаблона, похожий на rrowland's, но я чувствую, что мой алгоритм может быть немного быстрее. Он работает в O (n), используя умножение числа чисел для подсчета букв и не ветвящийся в самой продолжительной процедуре.

Вместо выполнения ind - 97 я сохраняю 97 свободных точек в массиве, к которому обращаются.

Я думаю, что если бы вы были более навязчивыми, вы могли бы делать подсчет, используя побитовые операции, но это достаточно хорошо.

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

Изменить 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;
  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;
}

Изменить 2

Я знаю, что это глупо, но добавление логарифмов простых чисел на самом деле немного быстрее. ( ориентир )

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

  var length1 = word1.length;
  var length2 = word2.length;

  var word1hash = 1;
  var word2hash = 1;

  var tab = {'q': 0.6931471805599453, 'w': 1.0986122886681098, 'e': 1.6094379124341003, 'r': 1.9459101490553132, 't': 2.3978952727983707, 'y': 2.5649493574615367, 'u': 2.833213344056216, 'i': 2.9444389791664403, 'o': 3.1354942159291497, 'p': 3.367295829986474, 'a': 3.4339872044851463, 's': 3.6109179126442243, 'd': 3.713572066704308, 'f': 3.7612001156935624, 'g': 3.8501476017100584, 'h': 3.970291913552122, 'j': 4.07753744390572, 'k': 4.110873864173311, 'l': 4.204692619390966, 'z': 4.2626798770413155, 'x': 4.290459441148391, 'c': 4.3694478524670215, 'v': 4.418840607796598, 'b': 4.48863636973214, 'n': 4.574710978503383, 'm': 4.61512051684126, 'Q': 0.6931471805599453, 'W': 1.0986122886681098, 'E': 1.6094379124341003, 'R': 1.9459101490553132, 'T': 2.3978952727983707, 'Y': 2.5649493574615367, 'U': 2.833213344056216, 'I': 2.9444389791664403, 'O': 3.1354942159291497, 'P': 3.367295829986474, 'A': 3.4339872044851463, 'S': 3.6109179126442243, 'D': 3.713572066704308, 'F': 3.7612001156935624, 'G': 3.8501476017100584, 'H': 3.970291913552122, 'J': 4.07753744390572, 'K': 4.110873864173311, 'L': 4.204692619390966, 'Z': 4.2626798770413155, 'X': 4.290459441148391, 'C': 4.3694478524670215, 'V': 4.418840607796598, 'B': 4.48863636973214, 'N': 4.574710978503383, 'M': 4.61512051684126, ' ': 0.0
}

  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: удалить равную длинупроверить.

ответил Simon Kuang 7 PM00000090000002031 2015, 21:08:20
1

У меня есть простой пример

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

ответил Shivek Parmar 8 ThuEurope/Moscow2016-12-08T14:54:02+03:00Europe/Moscow12bEurope/MoscowThu, 08 Dec 2016 14:54:02 +0300 2016, 14:54:02

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132