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