algorithm - 没有连续重复的字典顺序

Question

我知道字典顺序的算法，但是在这个问题中，我们可以不连续地重复字符。这让我感到困惑。

一个好的字符串 s 是：

1. 仅包含以下字母：[a,b,c]
2. 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

您可以按字典顺序对字符串列表进行排序。这些将包含具有相同连续字符的字符串。因此，在返回结果之前，您可以只创建另一个列表并遍历原始列表，同时仅将符合上述条件的字符串包含到新列表中。迭代整个列表后，只需将其返回，这将是您的最终答案。

例如。考虑一个列表 -

 ["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));