在给定字符串中寻找最优子串集

Question

我正在为给定的字符串寻找最优的字符串集.

给定字符串："FEEJEEDAI“

子字符串值：

铁-1 JE -2 JEE -3 AI -4 戴-6

可能的组合：

1) FE-JE-DAI - 1+2+6 =9 2) FE-JEE-DAI - 1+3+6 = 10 3) FE-JE-AI - 1+3+4 =8

最佳组合- 2) FE-JEE得分10

我觉得应该是这样的：

1)检查字符串是否包含特定的子字符串：

var string = "FEEJEEDAI", substring = "JE"; string.indexOf(substring) !== -1;

2)如果是真的，就找它的索引

var subStringIndex = string.indexOf(substring)

3)创建新的tempString来构建组合并“切断”substring与string的关系

var tempString = string.slice(subStringIndex, substring.length)

4)迭代string，寻找最优tempString

我不知道如何将它构建成循环，如何处理JEE和AI对DAI的情况

Answer 1

基本上，您可以使用一种迭代和递归的方法来获取字符串的所有可能的子字符串.。

该解决方案分为三部分。

1. 准备工作
2. 收集部件
3. 计算分数和创建结果集

准备工作

开始时，字符串的所有子字符串都收集在indices对象中。键是索引，值是有限制的对象，它是模式数组中字符串的最小长度。模式数组包含从该索引开始的索引和找到的子字符串。

第一个示例中的indices对象 { 0：{极限: 2，模式：{索引: 0，字符串："FE“}，3：{极限: 2，模式：{索引: 3，字符串："JE“}，{ index: 3，string："JEE”}，/* . */ }

收集部件

其主要思想是从索引0开始，使用一个空数组来收集子字符串。

若要检查组中哪些部分在一起，需要在给定索引处获取第一个子字符串或下一个关闭子字符串，然后使用极限属性(即最短子字符串的长度)，添加索引并将其作为搜索组成员的最大索引。

在第二个示例中，第一组由'FE'、'EE'和'EEJ'组成。 字符串注释

对于该组，将调用一个新的递归，该递归具有一个调整后的索引，并将子字符串连接到parts数组。

计算分数和创建结果集

如果没有找到更多的子字符串，则将各部分连接起来，计算分数并将其推送到结果集中。

解释结果 {部分：“0\FE_( /* . parts是索引和位置匹配字符串的组合。 在索引0处找到FE ^在索引3处找到JE ^在索引6处找到DAI score是根据给定的子字符串的权重计算的。 子串重量

示例三返回11个唯一的组合。

​

function getParts(string, weights) {

    function collectParts(index, parts) {
        var group, limit;
        while (index < string.length && !indices[index]) {
            index++;
        }
        if (indices[index]) {
            group = indices[index].pattern;
            limit = index + indices[index].limit;
            while (++index < limit) {
                if (indices[index]) {
                    group = group.concat(indices[index].pattern);
                }
            }
            group.forEach(function (o) {
                collectParts(o.index + o.string.length, parts.concat(o.index, o.string));
            });
            return;
        }
        result.push({
            parts: parts.join('|'),
            score: parts.reduce(function (score, part) { return score + (weights[part] || 0); }, 0)
        });
    }

    var indices = {},
        pattern,
        result = [];

    Object.keys(weights).forEach(function (k) {
        var p = string.indexOf(k);
        while (p !== -1) {
            pattern = { index: p, string: k };
            if (indices[p]) {
                indices[p].pattern.push(pattern);
                if (indices[p].limit > k.length) {
                    indices[p].limit = k.length;
                }
            } else {
                indices[p] = { limit: k.length, pattern: [pattern] };
            }
            p = string.indexOf(k, p + 1);
        }
    });
    collectParts(0, []);
    return result;
}

console.log(getParts("FEEJEEDAI", { FE: 1, JE: 2, JEE: 3, AI: 4, DAI: 6 }));
console.log(getParts("FEEJEEDAI", { FE: 1, JE: 2, JEE: 3, AI: 4, DAI: 6, EEJ: 5, EJE: 3, EE: 1 }));
console.log(getParts("EEEEEE", { EE: 2, EEE: 3 }));

.as-console-wrapper { max-height: 100% !important; top: 0; }

​

Answer 2

如果在找到子字符串时对子字符串进行切分，因为某些子字符串是其他子字符串的子字符串，那么首先搜索最大的子字符串。例如，如果你没有找到戴，你找到了人工智能，它就不可能是戴的一部分。您希望测试每个子字符串，这样您就可以将每个子字符串放入一个数组中，并遍历该数组。