我应该用JavaScript编写一个程序来查找所提供的一系列单词中的所有字谜。例如:“monk,konm,nkom,bbc,cbb,dell,ledl,llde”输出应分为几行:1。monk konm,nkom; bbc cbb;戴尔·莱尔,德尔
我已经将它们按字母顺序排序,即:“kmno kmno bbc bbc dell dell”并将它们放入一个数组中。
但是我仍然坚持比较和找到数组中匹配的anagram。
任何帮助将不胜感激。
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 />");
}
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"));
我有一个简单的例子
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
isAnagram使用reduce的另一种解决方案
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'));
var check=true;
var str="cleartrip";
var str1="tripclear";
if(str.length!=str1.length){
console.log("Not an anagram");
check=false;
}
console.log(str.split("").sort());
console.log("----------"+str.split("").sort().join(''));
if(check){
if((str.split("").sort().join(''))===((str1.split("").sort().join('')))){
console.log("Anagram")
}
else{
console.log("not a anagram");
}
}
这是我的解决方案,它解决了一个测试用例,其中输入字符串不是字谜,可以从输出中删除。因此输出仅包含anagram字符串。希望这是有帮助的。
/**
* Anagram Finder
* @params {array} wordArray
* @return {object}
*/
function filterAnagram(wordArray) {
let outHash = {};
for ([index, word] of wordArray.entries()) {
let w = word.split("").sort().join("");
outHash[w] = !outHash[w] ? [word] : outHash[w].concat(word);
}
let filteredObject = Object.keys(outHash).reduce(function(r, e) {
if (Object.values(outHash).filter(v => v.length > 1).includes(outHash[e])) r[e] = outHash[e]
return r;
}, {});
return filteredObject;
}
console.log(filterAnagram(['monk', 'yzx','konm', 'aaa', 'ledl', 'bbc', 'cbb', 'dell', 'onkm']));
我最近在编码面试中遇到过这个问题,这是我的解决方案。
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"]
]
这是我的看法:
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(“”)从数组中获取字符串。
我今天也在处理类似的问题,并希望分享我的工作成果。我只专注于检测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("");
}
我选择早期方法的原因是它对更大的字符串更有效,因为如果检测到任何可能的故障情况,您不需要对字符串进行排序,转换为数组或循环遍历整个字符串。
可能不是最有效的方式,但使用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());
}
我知道这是一个古老的帖子......但我刚刚在这次采访中被钉了。所以,这是我的“新的和改进的”答案:
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');
以下是上述输出:
toot是2个字谜集合的一部分:toto,toot。
pan是2个字谜集合的一部分:nap,pan。
视网膜是14种anagrams的集合的一部分:硬脂精,anestri,asterin,eranist,nastier,ratines,resiant,restain,retains,retinas,retsina,sainter,stainer,starnie。
哥们没有字谜。
我对这篇老帖子的解决方案:
// 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个单词 - >这是一个字谜。
我在接受采访时有这个问题。给定一系列单词['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"]
简单解决方案
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
也许这个?
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']
}
它是您想要的简单版本,当然可以改进,例如避免重复。