根据给定的前缀分离模式列表

Question

我有一个像这样的字符串有序列表，其中'-'的右侧数字可以增加到任何数字。

let arr = ['1-0/2-0/3-0', '1-0/2-0/3-1', '1-0/2-1/3-0', '1-1/2-0/3-0', '1-1/2-1/3-0', '1-1/2-1/3-1', '1-1/2-2/3-0']

我想将它们提取到一个基于前缀的数组/列表中，并按前缀后的直接数字对它们进行分组。

例如1：如果给定的前缀是1-，那么输出数组应该包含两个条目

[['1-0/2-0/3-0', '1-0/2-0/3-1', '1-0/2-1/3-0'], ['1-1/2-0/3-0', '1-1/2-1/3-0', '1-1/2-1/3-1', '1-1/2-2/3-0']]

例如2：如果给定的前缀是1-1/2-，那么输出数组应该包含三个条目

[['1-1/2-0/3-0'], ['1-1/2-1/3-0', '1-1/2-1/3-1'], ['1-1/2-2/3-0']]

我正在寻找比暴力方法更好的技巧(比如使用正则表达式(。

Answer 1

这里有一个简单的函数方法，可以用纯javascript实现这一点。我假设在列表中循环不算暴力。我还假设你想按前缀后的第一个字符分组，但这在你的问题中并不明确。基本上过滤掉无前缀的项目，并构建一个键控到前缀后第一个字符的对象：

let list = ["1-0/2-0/3-0","1-0/2-0/3-1","1-0/2-1/3-0","1-1/2-0/3-0","1-1/2-1/3-0","1-1/2-1/3-1","1-1/2-2/3-0"]
function segregate(prefix, list){
return Object.values(
list.filter(str => str.startsWith(prefix))
.reduce((obj, str) => {
let key = str[prefix.length]
if (!obj[key]) obj[key] = []
obj[key].push(str)
return obj
}, {})
)
}
console.log("with '1-'")
console.log(segregate("1-", list))
console.log("with '1-1/2-'")
console.log(segregate("1-1/2-", list))

Answer 2

让我们假设您只拥有一个项数组。然后使用startsWith:可以很容易地执行前缀匹配

const filtered = arr.filter(a => a.startsWith(prefix))

然后看起来您正在分组到前缀之后的第一个/。您可以使用reduce来完成此操作，但lodash中的groupBy使其非常容易。工作示例：

const arr = [
'1-0/2-0/3-0',
'1-0/2-0/3-1',
'1-0/2-1/3-0',
'1-1/2-0/3-0',
'1-1/2-1/3-0',
'1-1/2-1/3-1',
'1-1/2-2/3-0'
]
const prefix = '1-1/2-'
const filtered = arr.filter(a => a.startsWith(prefix))
const groups = _.groupBy(filtered, i => i.slice(prefix.length).split('/')[0])
const values = _.values(groups)
console.log(values)

<script src="https://cdn.jsdelivr.net/npm/lodash@4.17.10/lodash.min.js"></script>

Answer 3

另一种可能的解决方案是根据前缀创建一个树，如下所示：

{
'1': {
letters: ['1-0/2-0/3-0',
'1-0/2-0/3-1',
'1-0/2-1/3-0', ...]
children: {
'0/2': {
letters: [...],
children: {
...
}
}
...
}
}
}

然后给定一个前缀，我们可以遍历这棵树来找到合适的字母组。这种方法具有更好的运行时，因为您不需要遍历整个前缀列表(假设它比前缀的"深度"大得多(：

const strings = [
'1-0/2-0/3-0',
'1-0/2-0/3-1',
'1-0/2-1/3-0',
'1-1/2-0/3-0',
'1-1/2-1/3-0',
'1-1/2-1/3-1',
'1-1/2-2/3-0'
]
function insert(path, letter, tree) {
if (path.length > 0) {
let [node, ...remaining] = path;
if (node in tree) tree[node].letters.push(letter);
else tree[node] = {children: {}, letters: [letter]};
insert(remaining, letter, tree[node].children);
}
}
const prefixTree = strings.reduce((acc, curr) => {
insert(curr.split('-'), curr, acc);
return acc;
}, {});
function getLetters(prefix) {
function get(path, tree) {
if (path.length === 1)
return Object.values(tree[path[0]].children)
.map(v => v.letters);
return get(path.slice(1), tree[path[0]].children);
}
return get(prefix.split('-').filter(s => s !== ''), prefixTree);
}
console.log(getLetters('1-'));
console.log(getLetters('1-1/2-'));
console.log('Prefix tree looks like the following');
console.log(prefixTree);