没有连续重复的字典顺序

Question

我知道字典顺序算法，但是在这个问题中我们可以重复字符非consecutively.And这让我很困惑。

一个好的字符串 s 是：

仅包含集合中的这些字母：[a,b,c]
s[i] != s[i+1] 字符串 aba、bca、cbc 有效，但 aaa、abb、aab 无效。

集合顺序：[a, b, c]

["aba", "abc", "aca", "acb", "bab", "bac", "bca", "bcb", "cab", "cac", "cba", "cbc"].

你能帮我看看它的算法吗

Answer 1

听起来你想做的是使用字典顺序进行排序，然后过滤掉你认为无效的结果。

在您的示例中，第 1 步将是：

["aaa", "aab", "aac", ...]

然后删除无效的，你会得到：

["aba", "abc", "aca", ...]

Answer 2

您可以按字典顺序对字符串列表进行排序。这些将包含具有相同连续字符的字符串。因此，在 return 结果之前，您可以制作另一个列表并循环遍历原始列表，同时只将符合上述条件的字符串包含到新列表中。一旦你遍历了整个列表，就 return 它就是你的最终答案。

例如。考虑一个列表 -

 ["cab", "abc", "aca", "acc", "abb", "bbc", "caa", "aab"]

排序后-

['aab', 'abb', 'abc', 'aca', 'acc', 'bbc', 'caa', 'cab']

现在您可以遍历此列表并只选择符合您条件的元素。所以最终列表将是 -

['abc', 'aca', 'cab']

希望您理解该方法。

Answer 3

您可以使用递归算法，将上次使用的字母作为下一次选择的禁止字母传递。递归函数获取一个大小参数，因此它知道应该生成的字符串应该有多长。然后它迭代每个可能的字符，但排除禁止的字符，并递归调用函数，但大小减小。当前字符现在成为递归调用的禁止字符。当该调用返回结果时，它会在每个结果前加上当前字符作为前缀，以便有效地将它们的大小都增加一个字符。对于迭代的所有其他字符（禁止的字符除外）重复此操作。并将所有这些结果收集到一个结果集（数组）中，并返回。

我假设字符集是按字典顺序提供的（否则在使用下面的算法之前对其进行排序），并且生成的字符串的大小也是给算法的参数。

这是该想法的一个简单 JavaScript 实现：

function combis(chars, size, forbidden="") {
    if (size == 0) { // base case
        return [""];
    }
    let results = [];
    for (let chr of chars) {
        if (chr != forbidden) { // Avoid repetition
            for (let combi of combis(chars, size-1, chr)) {
                results.push(chr + combi); // prefix the returned string
            }
        }
    }
    return results;
}

console.log(combis("abc", 3));

没有连续重复的字典顺序

Lexicographic ordering with no consecutive repetition

algorithm

data-structures

lexicographic

lexicographic-ordering