一尘不染

测试字符串中的重复字符

algorithm

我正在处理字符串,并且有一种情况需要确定一个字符串(通常是一个小于10个字符的小字符串)是否包含重复的字符。

`ABCDE`  // does not contain repeats 
`AABCD`  // does contain repeats, ie A is repeated

我可以遍历string.ToCharArray()并针对char
[]中的每个其他字符测试每个字符,但是我感觉好像缺少了一些明显的东西……也许我只需要喝咖啡。有人可以帮忙吗?

编辑:

字符串将被排序,因此顺序并不重要,因此ABCDA => AABCD

重复的频率也很重要,因此我需要知道重复是成对的还是三联体等。


阅读 197

收藏
2020-07-28

共1个答案

一尘不染

如果字符串较短,则仅循环和测试可能是最简单,最有效的方法。我的意思是,您 可以
创建一个哈希集(在您使用的任何平台上)并遍历字符,如果字符已经在字符集中,则失败,否则将其添加到字符集中-但这仅可能在字符串更长。

编辑:现在我们知道它的排序,mquander的答案是最好的IMO。这是一个实现:

public static bool IsSortedNoRepeats(string text)
{
    if (text.Length == 0)
    {
        return true;
    }
    char current = text[0];
    for (int i=1; i < text.Length; i++)
    {
        char next = text[i];
        if (next <= current)
        {
            return false;
        }
        current = next;
    }
    return true;
}

如果您不介意重复使用索引器,则可以使用更短的替代方法:

public static bool IsSortedNoRepeats(string text)
{
    for (int i=1; i < text.Length; i++)
    {
        if (text[i] <= text[i-1])
        {
            return false;
        }
    }
    return true;
}

编辑:好的,在“频率”方面,我将问题转一圈。我仍然假设该字符串已排序,因此我们想知道的是最长运行时间的长度。如果没有重复,则最长运行长度将为0(对于空字符串)或1(对于非空字符串)。否则,它将为2或更大。

首先是特定于字符串的版本:

public static int LongestRun(string text)
{
    if (text.Length == 0)
    {
        return 0;
    }
    char current = text[0];
    int currentRun = 1;
    int bestRun = 0;

    for (int i=1; i < text.Length; i++)
    {
        if (current != text[i])
        {
            bestRun = Math.Max(currentRun, bestRun);
            currentRun = 0;
            current = text[i];
        }
        currentRun++;
    }
    // It's possible that the final run is the best one
    return Math.Max(currentRun, bestRun);
}

现在我们也可以将其作为通用扩展方法IEnumerable<T>

public static int LongestRun(this IEnumerable<T> source)
{
    bool first = true;
    T current = default(T);
    int currentRun = 0;
    int bestRun = 0;

    foreach (T element in source)
    {
        if (first || !EqualityComparer<T>.Default(element, current))
        {
            first = false;
            bestRun = Math.Max(currentRun, bestRun);
            currentRun = 0;
            current = element;
        }
    }
    // It's possible that the final run is the best one
    return Math.Max(currentRun, bestRun);
}

然后您可以拨打电话"AABCD".LongestRun()

2020-07-28