我有一个将近2700个字符串的数组,我需要为一个句子的anagram找到正确的短语这个列表是一个排序的列表,包含了将近10万个项目,其中包含了可以容纳的单词。
我想把它们组合成1,2和3个单词,如果它们符合我的字谜长度,就匹配单词的长度,并用空格来修饰。
我尝试了此功能,但在内存中失败,我是否可以设置最多3个单词来匹配:
var permutations = require('./permutations.js').permutations;
var shortList = words.slice(10, 20);
var result = permutations(shortList);
console.log(result);
在permutation.js中
(function (exports) {
'use strict';
var permutations = (function () {
var res;
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function permutations(arr, current) {
if (current >= arr.length) {
return res.push(arr.slice());
}
for (var i = current; i < arr.length; i += 1) {
swap(arr, i, current);
permutations(arr, current + 1);
swap(arr, i, current);
}
}
return function (arr) {
res = [];
permutations(arr, 0);
var temp = res;
// Free the extra memory
res = null;
return temp;
};
}());
exports.permutations = permutations;
}((typeof window === 'undefined') ? module.exports : window));
编辑:
例子
var input = ['test', 'foo', 'bar', 'hello', 'world'];
var output = magicFunc(input);
// console.log(output);
//
// [['test foo bar'],
// ['test foo hello'],
// ['test foo world'],
// ['test bar foo'],
// ['test bar hello'],
// ['test bar world']...];
最佳答案
三个字的所有排列都是三=6个
所有10万字的组合选3就是10万字/6(99996!)~=1.66E14
所以最终的输出是1.66e14*6~=9.99e14
试图创建一个由1万亿个字符串数组组成的列表是计算机无法处理的。
我试过这个功能,但记忆犹新
是轻描淡写的
你必须对你的单词列表做一些预处理用字母和长度来划分它们。然后对你的字谜进行更集中的搜索。
最后,不要对此使用递归(这是不必要的,而且它会更快地使用内存,因为每次调用都会创建堆栈帧。
只需使用循环三次,你就可以得到所有的结果-张大伟
for(var i = 0; i < list.length; i++) {
var wi = list[i];
for(var j = i + 1; j < list.length; j++) {
var wj = list[j];
for(var k = j + 1; k < list.length; k++) {
var wk = list[k];
// hard coded 6 permutations
var p1 = wi + wj + wk;
var p2 = wi + wk + wj;
var p3 = wj + wi + wk;
var p4 = wj + wk + wi;
var p5 = wk + wi + wj;
var p6 = wk + wj + wi;
// check p1 - p6 for your anagram condition
...
}
}
}
关于javascript - 很长的排列-句子字谜,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/32009166/