javascript - 在给定字符串中找到最佳子串集

Question

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

Given string: "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) 如果为真，找到它的索引

var subStringIndex = string.indexOf(substring)

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

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

4) 遍历 string 并找到最优的 tempString

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

Answer 1

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

这个解决方案分为三个部分

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

---

准备

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

indices object from the first example

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

收集零件

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

要检查哪些部分在一组中，您需要获取给定索引处的第一个子字符串或下一个接近的子字符串，然后采用 limit 属性，即最短子字符串的长度，添加索引和将其作为搜索群成员的最大索引。

From the second example the first group consists of 'FE', 'EE' and '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

使用该组调用新的递归，调整索引并将子字符串连接到部分数组。

计算分数并创建结果集

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

Interpreting the result

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

parts are a combination of indices and matching strings at the position

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

score is calculated with the given weights of the substrings

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; }