在给定字符串中查找最佳子串集

Question

我正在尝试为给定的字符串找到最佳字符串集.

给定字符串:"FEEJEEDAI"

子串值:

FE - 1
JE - 2
JEE - 3
AI - 4
DAI - 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-DAI]得分10

我认为它应该是这样的:

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

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

2)如果为true则找到它的索引

var subStringIndex = string.indexOf(substring)

3)创建新的tempString以构建组合并substring从中"切断"string

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

4)迭代string并找到最佳tempString

我不知道如何将它构建到循环中并处理情况JE vs JEE,AI vs DAI

Answer 1

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

该解决方案分为3个部分

1. 制备
2. 收集零件
3. 计算分数并创建结果集

制备

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

indices 第一个例子中的对象

{
    0: {
        limit: 2,
        pattern: [
            {
                index: 0,
                string: "FE"
            }
        ]
    },
    3: {
        limit: 2,
        pattern: [
            {
                index: 3,
                string: "JE"
            },
            {
                index: 3,
                string: "JEE"
            }
        ]
    },
    /* ... */
}

收集零件

主要思想是从索引零开始,使用空数组来收集子字符串.

要检查哪些部分在一个组中,您需要获取给定索引的第一个子字符串或下一个关闭的子字符串,然后获取limit属性,即最短子字符串的长度,添加索引并将其作为搜索组成员的最大索引.

从第二个例子中,第一组包括'FE','EE'并'EEJ'

string      comment
----------  -------------------------------------
01 2345678  indices
FE|EJEEDAI  
FE|         matching pattern FE  at position 0
 E|E        matching pattern EE  at position 1
 E|EJ       matching pattern EEJ at position 1
^^          all starting substrings are in the same group

使用该组,将调用新的递归,调整索引并将子字符串连接到parts数组.

计算分数并创建结果集

如果找不到更多子字符串,则连接部件并计算分数并将其推送到结果集.

解释结果

 [
    {
        parts: "0|FE|3|JE|6|DAI",
        score: 9
    },
    /* ... */
]

parts 是位置处的索引和匹配字符串的组合

 0|FE|3|JE|6|DAI
 ^ ^^            at index 0 found FE
      ^ ^^       at index 3 found JE
           ^ ^^^ at index 6 found DAI

score 用给定的子串的权重计算

substring  weight
---------  ------
 FE            1
 JE            2
 DAI           6
---------  ------
score          9

示例三返回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; }