Trova anagrammi in javascript

Question

Devo scrivere un programma in JavaScript per trovare tutti gli anagrammi all'interno di una serie di parole fornite. ad es .: "monaco, konm, nkom, bbc, cbb, dell, ledl, llde" L'output dovrebbe essere classificato in righe: 1. monk konm, nkom; 2. bbc cbb; 3. dell ledl, llde;

Li ho già ordinati in ordine alfabetico e cioè: "kmno kmno bbc bbc dell" e li metto in un array.

Tuttavia, sono bloccato nel confrontare e trovare l'anagramma corrispondente all'interno dell'array.

Qualsiasi aiuto sarà molto apprezzato.

Answer 1

oggetti JavaScript sono eccellenti per questo scopo, dal momento che sono essenzialmente negozi chiave/valore:

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

Qui è il mio introito:

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 + ")"); 
     } 
    } 
} 

dove l'uscita sarebbe (la parola, i corrispondenza e l'indice di entrambi):

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

Per ottenere i caratteri in ordine alfabetico, I split utilizzato ("") per ottenere un array, chiamato sort() e join utilizzato ("") per ottenere una stringa dall'array.

Answer 3

So che questo è un post antico ... ma recentemente sono stato inchiodato durante un'intervista su questo. Quindi, ecco la mia 'nuova & migliorato' risposta:

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

Ecco come viene eseguito:

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

Ecco l'output di quanto sopra:

toot fa parte di una raccolta di 2 anagrammi : toto, toot.

pan fa parte di una raccolta di 2 anagrammi: pisolino, padella.

retine fa parte di una collezione di 14 anagrammi: stearina, anestri, asterin, eranist, più cattivo, ratines, resiant, restain, conserva, retine, retsina, sainter, Stainer, starnie.

buddy non ha anagrammi.

Answer 4

Oggi ho lavorato a una domanda simile e volevo condividere i risultati del mio lavoro. Ero concentrato nel rilevare solo l'anagramma, in modo che l'elaborazione dell'elenco di parole non facesse parte del mio esercizio, ma questo algoritmo dovrebbe fornire un modo altamente performante per rilevare un anagramma tra due parole.

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

Credo che tecnicamente si può essere risolto in questo modo:

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

La ragione per cui ho scelto l'approccio precedente è che è più performante per le stringhe più grandi dal momento che non c'è bisogno di ordinare o stringa , converti in una matrice o fai un ciclo attraverso l'intera stringa se viene rilevato un eventuale caso di errore.

Answer 5

La mia soluzione a questo vecchio post:

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

Fondamentalmente ho normalizzare ogni parola di classificare i suoi personaggi in modo StackOverflow sarebbe acefkloorstvw, costruire una mappa tra le parole normalizzate e le parole originali, determinare quale parola normalizzata ha più di 1 parola allegata ad esso -> Questo è un anagramma.

Answer 6

Ho avuto questa domanda in un'intervista. Data una serie di parole ['gatto', 'cane', 'tac', 'dio', 'atto'], restituisce un array con tutti gli anagrammi raggruppati insieme. Fa in modo che gli anagrammi siano unici.

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

non

Probabilmente il modo più efficiente, ma un modo chiaro intorno usando 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

Ho un esempio facile

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 ; 

} 

funzione di chiamata sarà isAnagram("Army",Mary); Funzione restituirà true o false

Answer 10

Forse questo?

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 

Sarebbe tornare qualcosa di simile

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

Si tratta di una semplice versione di quello che volevi e certamente potrebbe essere migliorata evitando duplicati per esempio.

Answer 11

Un'altra soluzione per ridurre isAnagram utilizzando

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