javascript - 如何通过改变 JavaScript 中的一个字符来排列字符串?
问题描述
对于所有字符串操作大师来说,这可能是一个有趣的练习。给定一个包含散布在准随机位置的“x”或“xx”的字符串(如DNA 序列),我需要通过改变其中的“x”来排列该字符串。"x" 的每个实例可以是单数 "x" 或双 "xx",并且整个字符串应包含 "x" 和 "xx" 的所有可能组合。
给定字符串“ooxooxoo”,输出将是
[
"ooxxooxoo",
"ooxooxxoo",
"ooxxooxxoo"
]
给定字符串“ooxxooxoo”,输出将是
[
"ooxooxoo",
"ooxooxxoo",
"ooxxooxxoo"
]
给定字符串“ooxooxoox”,输出将是
[
"ooxxooxoox",
"ooxooxxoox",
"ooxooxooxx",
"ooxxooxxoox",
"ooxxooxooxx",
"ooxooxxooxx",
"ooxxooxxooxx"
]
依此类推。在任何情况下,输出都不应包含三个或更多连续的 x。
更新:
经过一番研究,我确定了一个基于堆排列算法的解决方案:
function heapsPermute(aInput, aOutput, n) {
var swap = function(n1, n2) {
var sTemp = aInput[n1];
aInput[n1] = aInput[n2];
aInput[n2] = sTemp;
};
n = n || aInput.length;
if (n===1) {
// Add only unique combination
var sCombo = aInput.join(' ');
if (aOutput.indexOf(sCombo)<0) aOutput.push(sCombo);
} else {
for (var i=1, j; i<=n; ++i) {
heapsPermute(aInput, aOutput, n-1);
j = (n%2) ? 1 : i;
swap(j-1, n-1);
}
}
}
function permuteChar(sChar, sSource) {
var aCombos = [],
aMatchIndexes = [],
aPermutations = [],
aResults = [],
nMatches,
reMatch = new RegExp(sChar + '+', 'gi');
// Find matches
while (oMatch = reMatch.exec(sSource)) {
aMatchIndexes.push(oMatch.index);
}
nMatches = aMatchIndexes.length;
if (!nMatches) return;
// Generate combinations
aCombos.push(Array.apply(null, Array(nMatches)).map(function() {
return sChar;
}));
for (var i=0; i<nMatches; ++i) {
aCombos.push([]);
for (var j=0; j<nMatches; ++j) {
aCombos[aCombos.length-1].push((i<j)?sChar:sChar+sChar);
}
}
// Build list of permutations
for (var i=0; i<aCombos.length; ++i) {
heapsPermute(aCombos[i], aPermutations);
}
// Search and replace!
for (var i=0, j, a; i<aPermutations.length; ++i) {
a = aPermutations[i].split(' ');
j = 0;
aResults.push(sSource.replace(reMatch, function(sMatch) {
return sMatch.replace(reMatch, a[j++])
}));
}
return aResults;
}
console.log(permuteChar('x', 'ooxxooxoox'));
然后我看到 melpomene 的解决方案有一个很好的解释,它更加简洁和优雅,所以这是我要接受的解决方案。对于那些仍在使用 ES5 的人,这是我的 ES5 版本的 melpomene 函数:
function charVariants(sChar, sSource) {
var aChunks = sSource.split(new RegExp(sChar + '+', 'i')),
aResults = [aChunks.shift()];
for (var i=0, a; i<aChunks.length; ++i) {
a = [];
for (var j=0; j<aResults.length; ++j) {
a.push(
aResults[j] + sChar + aChunks[i],
aResults[j] + sChar + sChar + aChunks[i]
);
}
aResults = a;
}
return aResults;
}
console.log(charVariants('x', 'ooxxooxoox'));
感谢所有花时间提供帮助的人。
解决方案
我会考虑制作一个简单的递归函数,在遍历字符串时跟踪它的位置。就像是:
function doublex(str, index=0, strings = []){
for (let i = index; i < str.length; i++){
if (str[i] === 'x'){
let d = str.slice(0,i) + 'x' + str.slice(i)
strings.push(d)
doublex(d, i+2, strings)
}
}
return strings
}
// two x
console.log(doublex('ooxooxoo'))
// three x
console.log(doublex('ooxoxoxoo'))
推荐阅读
- javascript - React Router 嵌套路由
- gatsby - 关于将 Gatsby 用于动态应用程序的信息
- image-processing - 为什么添加椒盐噪声必须在灰度图像上?
- jquery - Coldfusion Ajax-Request 抛出 JSON.parse 错误
- grails - 如何在循环中使用生成的 grails 3 服务在数据库中存储多个条目
- java - 如何从 @PreMatching 过滤器中的 ContainerRequestContext 更改路径参数?
- load-testing - 哪些负载测试工具可以使用来自 S3 的 AWS ALB 日志
- java - Spring webflux:如何在ResponseEntityResultHandler中使用自定义jackson ObjectWriter?
- javascript - 使用 PDF.js 查看器显示受保护资源提供的 pdf
- php - 附加区域的自动年龄计算