在JavaScript中的Anagrams查找器

Question

我应该用JavaScript编写一个程序来查找所提供的一系列单词中的所有字谜.例如:"monk,konm,nkom,bbc,cbb,dell,ledl,llde"输出应分为几行:1.monk konm,nkom; bbc cbb; 戴尔·莱尔,德尔

我已将它们按字母顺序排序,即:"kmno kmno bbc bbc dell dell"并将它们放入数组中.

但是我仍然坚持比较和找到数组中匹配的anagram.

任何帮助将不胜感激.

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

简单的解决方案

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 3

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 4

我今天也在处理类似的问题,并希望分享我的工作成果.我只专注于检测anagram,因此处理单词列表不是我练习的一部分,但是这个算法应该提供一种高效的方法来检测两个单词之间的字谜.

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

可能不是最有效的方式,但使用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());
}