Поиск анаграмм в JavaScript

Question

Я должен написать программу на JavaScript, чтобы найти все анаграммы в предоставленной серии слов. Например: "Монах, Конм, Нком, Би-би-си, КББ, Делл, Ледл, Ильде" Вывод должен быть разбит на строки: 1. монах конм, нком; 2. БиБиСи КББ; 3. dell ledl, llde;

Я уже отсортировал их в алфавитном порядке, т.е. "кмно кмно bbc bll dell dell" и поместите их в массив.

Однако я застрял в сравнении и нахождении подходящей анаграммы в массиве.

Любая помощь будет принята с благодарностью.

Answer 1

Вот мой дубль:

var input = "monk, konm, bbc, cbb, dell, ledl";
var words = input.split(", ");

for ( var i = 0; i < words.length; i++) {

    var word = words[i];
    var alphabetical = word.split("").sort().join("");

    for (var j = 0; j < words.length; j++) {

        if (i === j) {
            continue;
        }

        var other = words[j];
        if(alphabetical === other.split("").sort().join("")){
            console.log(word + " - " + other + " (" + i + ", " + j + ")");
        }
    }
}

где будет вывод (слово, совпадение и индекс обоих):

monk - konm (0, 1)
konm - monk (1, 0)
bbc - cbb (2, 3)
cbb - bbc (3, 2)
dell - ledl (4, 5)
ledl - dell (5, 4)

Чтобы получить символы в алфавитном порядке, я использовал split ("") или массив, называемый sort (), и использовал join (""), чтобы получить строку из массива.

Answer 2

Объекты Javascript отлично подходят для этой цели, поскольку они по сути являются хранилищами ключей / значений:

// Words to match
var words = ["dell", "ledl", "abc", "cba"];

// The output object
var anagrams = {};

for (var i in words) {
    var word = words[i];

    // sort the word like you've already described
    var sorted = sortWord(word);

    // If the key already exists, we just push
    // the new word on the the array
    if (anagrams[sorted] != null) {
        anagrams[sorted].push(word);
    } 
    // Otherwise we create an array with the word
    // and insert it into the object
    else {
        anagrams[sorted] = [ word ];
    }
}

// Output result
for (var sorted in anagrams) {
    var words = anagrams[sorted];
    var sep = ",";
    var out = "";
    for (var n in words) {
        out += sep + words[n];
        sep = "";
    }
    document.writeln(sorted + ": " + out + "<br />");
}

Answer 3

Сегодня я проработал вопрос, похожий на этот, и хотел поделиться результатами своей работы. Я был сосредоточен на обнаружении анаграммы, поэтому обработка списка слов не была частью моего упражнения, но этот алгоритм должен обеспечить высокоэффективный способ обнаружения анаграммы между двумя словами.

function anagram(s1, s2){
  if (s1.length !== s2.length) {
    // not the same length, can't be anagram
    return false;
  }
  if (s1 === s2) {
    // same string must be anagram
    return true;
  }

  var c = '',
    i = 0,
    limit = s1.length,
    match = 0,
    idx;
  while(i < s1.length){
    // chomp the next character
    c = s1.substr(i++, 1);
    // find it in the second string
    idx = s2.indexOf(c);
    if (idx > -1) {
      // found it, add to the match
      match++;
      // assign the second string to remove the character we just matched
      s2 = s2.substr(0, idx) + s2.substr(idx + 1);
    } else {
      // not found, not the same
      return false;
    }
  }
  return match === s1.length;
}

Я думаю, что технически это можно решить следующим образом:

function anagram(s1, s2){
  return s1.split("").sort().join("") === s2.split("").sort().join("");
}

Причина, по которой я выбрал предыдущий подход, заключается в том, что он более производителен для больших строк, поскольку вам не нужно сортировать строку, преобразовывать ее в массив или проходить по всей строке, если обнаружен какой-либо возможный случай отказа. *

Answer 4

Вероятно, не самый эффективный способ, но ясный способ использования es6

function sortStrChars(str) {
    if (!str) {
        return;
    }
    str = str.split('');
    str = str.sort();
    str = str.join('');
    return str;
}

const words = ["dell", "ledl", "abc", "cba", 'boo'];

function getGroupedAnagrams(words){
    const anagrams = {}; // {abc:[abc,cba], dell:[dell, ledl]}
    words.forEach((word)=>{
        const sortedWord = sortStrChars(word);
        if (anagrams[sortedWord]) {
            return anagrams[sortedWord].push(word);
        }
        anagrams[sortedWord] = [word];
    });
    return anagrams;
}

const groupedAnagrams = getGroupedAnagrams(words);
for(const sortedWord in groupedAnagrams){
    console.log(groupedAnagrams[sortedWord].toString());
}

Answer 5

Я знаю, что это древний пост ... но я только недавно был заколочен во время интервью по этому поводу. Итак, вот мой «новый и улучшенный» ответ:

var AnagramStringMiningExample = function () {

/* Author: Dennis Baughn
*  This has also been posted at: 
*  /742634/poisk-anagramm-v-javascript

*  Free, private members of the closure and anonymous, innner function
*  We will be building a hashtable for anagrams found, with the key 
*  being the alphabetical char sort (see sortCharArray()) 
*  that the anagrams all have in common. 
*/
    var dHash = {};

    var sortCharArray = function(word) {
        return word.split("").sort().join("");
    };

/* End free, private members for the closure and anonymous, innner function */

/* This goes through the dictionary entries. 
 *  finds the anagrams (if any) for each word,
 *  and then populates them in the hashtable. 
 *  Everything strictly local gets de-allocated 
 *  so as not to pollute the closure with 'junk DNA'.
*/
    (function() {
       /* 'dictionary' referring to English dictionary entries. For a real 
        *  English language dictionary, we could be looking at 20,000+ words, so 
        *  an array instead of a string would be needed.
        */
       var dictionaryEntries = "buddy,pan,nap,toot,toto,anestri,asterin,eranist,nastier,ratines,resiant,restain,retains,retinas,retsina,sainter,stainer,starnie,stearin";
       /* This could probably be refactored better.  
        * It creates the actual hashtable entries. */
       var populateDictionaryHash = function(keyword, newWord) {
          var anagrams = dHash[keyword];
          if (anagrams && anagrams.indexOf(newWord) < 0) 
            dHash[keyword] = (anagrams+','+newWord);
          else dHash[keyword] = newWord;
       };

       var words = dictionaryEntries.split(",");

       /* Old School answer, brute force
       for (var i = words.length - 1; i >= 0; i--) {
        var firstWord = words[i];
        var sortedFirst = sortCharArray(firstWord);
        for (var k = words.length - 1; k >= 0; k--) {
               var secondWord = words[k];
           if (i === k) continue;
            var sortedSecond = sortCharArray(secondWord);
            if (sortedFirst === sortedSecond)   
                       populateDictionaryHash(sortedFirst, secondWord);
        }
       }/*

        /*Better Method for JS, using JS Array.reduce(callback) with scope binding on callback function */
        words.reduce(function (prev, cur, index, array) { 
            var sortedFirst = this.sortCharArray(prev);
            var sortedSecond = this.sortCharArray(cur); 
            if (sortedFirst === sortedSecond) {
                var anagrams = this.dHash[sortedFirst];
                if (anagrams && anagrams.indexOf(cur) < 0) 
                   this.dHash[sortedFirst] = (anagrams + ',' + cur);
                else 
                   this.dHash[sortedFirst] = prev + ','+ cur;                    
            }
            return cur;
        }.bind(this));
    }());

    /* return in a nice, tightly-scoped closure the actual function 
     *  to search for any anagrams for searchword provided in args and render results. 
    */
    return function(searchWord) {
       var keyToSearch = sortCharArray(searchWord);
       document.writeln('<p>');
       if (dHash.hasOwnProperty(keyToSearch)) {
        var anagrams = dHash[keyToSearch];
        document.writeln(searchWord + ' is part of a collection of '+anagrams.split(',').length+' anagrams: ' + anagrams+'.');
       } else document.writeln(searchWord + ' does not have anagrams.');
       document.writeln('<\/p>');
    };
};

Вот как это выполняется:

var checkForAnagrams = new AnagramStringMiningExample();
checkForAnagrams('toot');
checkForAnagrams('pan');
checkForAnagrams('retinas');
checkForAnagrams('buddy');

Вот результат вышеупомянутого:

toot является частью коллекции из 2 анаграммы: toto, toot.

кастрюля является частью коллекции из 2 анаграммы: дремота, пан.

сетчатки является частью коллекции из 14 анаграммы: стеарин, anestri, asterin, eranist, гаже, ratines, resiant, restain, сохраняет, сетчатку, рецина, sainter, ситечко, starnie.

у приятеля нет анаграмм.

Answer 6

У меня был этот вопрос в интервью. Учитывая массив слов ['cat', 'dog', 'tac', 'god', 'act'], верните массив со всеми анаграммами, сгруппированными вместе. Уверен, что анаграммы уникальны.

var arr = ['cat', 'dog', 'tac', 'god', 'act'];

var allAnagrams = function(arr) {
    var anagrams = {};
    arr.forEach(function(str) {
        var recurse = function(ana, str) {
            if (str === '') 
                anagrams[ana] = 1;
            for (var i = 0; i < str.length; i++)
                recurse(ana + str[i], str.slice(0, i) + str.slice(i + 1));
        };
        recurse('', str);
    });
    return Object.keys(anagrams);
}

console.log(allAnagrams(arr));
//["cat", "cta", "act", "atc", "tca", "tac", "dog", "dgo", "odg", "ogd", "gdo", "god"]

Answer 7

Мое решение этого старого поста:

// Words to match
var words = ["dell", "ledl", "abc", "cba"],
    map = {};

//Normalize all the words 
var normalizedWords = words.map( function( word ){
  return word.split('').sort().join('');
});

//Create a map: normalizedWord -> real word(s)
normalizedWords.forEach( function ( normalizedWord, index){
  map[normalizedWord] = map[normalizedWord] || [];
  map[normalizedWord].push( words[index] );
});

//All entries in the map with an array with size > 1 are anagrams
Object.keys( map ).forEach( function( normalizedWord , index  ){
  var combinations = map[normalizedWord];
  if( combinations.length > 1 ){
    console.log( index + ". " + combinations.join(' ') );
  }
});

Обычно я нормализую каждое слово, сортируя его символы таким образом, чтобы stackoverflow был бы acefkloorstvw , строил карту между нормализованными словами и исходными словами, определял, в каком нормализованном слове более 1 слова прикрепленный к нему -> Это анаграмма.

Answer 8

Простое решение

function anagrams(stringA, stringB) {
    return cleanString(stringA) === cleanString(stringB);
}

function cleanString(str) {
    return str.replace(/[^\w]/g).toLowerCase().split('').sort().join()
}   

anagrams('monk','konm')

Если это функция anagrams, то она вернет true, иначе false

Answer 9

Может быть, это?

function anagram (array) {
    var organized = {};
    for (var i = 0; i < array.length; i++) {
        var word = array[i].split('').sort().join('');
        if (!organized.hasOwnProperty(word)) {
            organized[word] = [];
        }
        organized[word].push(array[i]);
    }    
    return organized;
}


anagram(['kmno', 'okmn', 'omkn', 'dell', 'ledl', 'ok', 'ko']) // Example

Это вернуло бы что-то вроде

{
    dell: ['dell', 'ledl'],
    kmno: ['kmno', okmn', 'omkn'],
    ko: ['ok', ko']
}

Это простая версия того, что вы хотели, и, конечно, ее можно улучшить, избегая, например, дубликатов.

Answer 10

Я недавно сталкивался с этим в интервью по кодированию, вот мое решение.

    function group_anagrams(arr) {
      let   sortedArr = arr.map(item => item.split('').sort().join(''));
      let setArr = new Set(sortedArr);
      let reducedObj = {};
      for (let setItem of setArr) {
        let indexArr = sortedArr.reduce((acc, cur, index) => {
          if (setItem === cur) {
            acc.push(index);
          }
          return acc;
        }, []);
        reducedObj[setItem] = indexArr;
      }
      let finalArr = [];
      for (let reduceItem in reducedObj) {
        finalArr.push(reducedObj[reduceItem].map(item => arr[item]));
      }
      return finalArr;
    }
    group_anagrams(['car','cra','rca', 'cheese','ab','ba']);

будет выглядеть как

[
  ["car", "cra", "rca"],
  ["cheese"],
  ["ab", "ba"]
]