javascript中的Anagrams查找器

Question

我应该用JavaScript编写一个程序来查找所提供的一系列单词中的所有anagrams。例如：“monk，konm，nkom，bbc，cbb，dell，ledl，llde” 输出应分类为： 1. monk konm，nkom; 2. bbc cbb; 3. dell ledl，llde;

我已经将它们按字母顺序排序，即： “kmno kmno bbc bbc dell dell” 并将它们放入数组中。

但是我被困在比较和在数组中找到匹配的anagram。

任何帮助将不胜感激。

Answer 1

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 2

这是我的看法：

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 3

我知道这是一个古老的帖子......但我最近在接受采访时被钉上了这一张。所以，这里是我的'新&改进的回答：

var AnagramStringMiningExample = function() { 

/* Author: Dennis Baughn 
* This has also been posted at: 
* http://stackoverflow.com/questions/909449/anagrams-finder-in-javascript/5642437#5642437 

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

这里是上面的输出：

嘟嘟是2 anagrams的集合的一部分：托托，嘟嘟。

潘是一个集合的一部分2 anagrams：nap，pan。

视网膜是14个 字谜集合的一部分： 硬脂精，anestri，asterin，eranist，厉害，ratines，resiant，复染，保留，视网膜，retsina，sainter，染色，starnie。

好友没有字谜。

Answer 4

我今天通过类似的问题工作，想分享我的工作成果。我专注于检测字谜，因此处理单词列表并不是我练习的一部分，但是这种算法应该提供一种非常高效的方式来检测两个单词之间的谜语。

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 5

我解决了这个旧帖子：

// 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(' ')); 
    } 
}); 

基本上我正常化的每一个字的排序其字符，从而计算器将acefkloorstvw，建立规范化的词与原词之间的映射，确定哪些规范化的单词有超过1个单词附加到它 - >这是一个字谜。

Answer 6

我在面试中有过这个问题。给定一组单词['cat'，'dog'，'tac'，'god'，'act']，返回一个数组，并将所有的字符组合在一起。确保anagrams是独一无二的。

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

function isAnagram(str1, str2) { 
    var str1 = str1.toLowerCase(); 
    var str2 = str2.toLowerCase(); 

    if (str1 === str2) 
    return true; 

    var dict = {}; 

    for(var i = 0; i < str1.length; i++) { 
    if (dict[str1[i]]) 
     dict[str1[i]] = dict[str1[i]] + 1; 
    else 
     dict[str1[i]] = 1; 
    } 

    for(var j = 0; j < str2.length; j++) { 
    if (dict[str2[j]]) 
     dict[str2[j]] = dict[str2[j]] - 1; 
    else 
     dict[str2[j]] = 1; 
    } 

    for (var key in dict) { 
    if (dict[key] !== 0) 
     return false; 
    } 

    return true; 
} 

console.log(isAnagram("hello", "olleh")); 

Answer 8

可能不是最有效的方式，但各地使用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 9

一个明确的办法，我有一个简单的例子

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

Answer 10

也许这样？

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 11

为isAnagram使用另一种解决方案减少

const checkAnagram = (orig, test) => { 
    return orig.length === test.length 
    && orig.split('').reduce(
     (acc, item) => { 
     let index = acc.indexOf(item); 
     if (index >= 0) { 
      acc.splice(index, 1); 
      return acc; 
     } 
     throw new Error('Not an anagram'); 
     }, 
     test.split('') 
    ).length === 0; 
}; 

const isAnagram = (tester, orig, test) => { 
    try { 
    return tester(orig, test); 
    } catch (e) { 
    return false; 
    } 
} 

console.log(isAnagram(checkAnagram, '867443', '473846')); 
console.log(isAnagram(checkAnagram, '867443', '473846')); 
console.log(isAnagram(checkAnagram, '867443', '475846'));