时间戳

首页 > 解决方案 > 如何优化这段 C# 代码，使其运行时间不会太长？

c# - 如何优化这段 C# 代码，使其运行时间不会太长？

问题描述

任务是：

给定两个字符串数组，确定对应元素是否包含公共子字符串

我的代码是（方法给了，我应该填写）：

public static void commonSubstring(List<string> a, List<string> b) { 
    string[] listA = a.ToArray(); 
    string[] listB = b.ToArray(); 
    bool contains = false;
    
    for(int i = 0; i < listA.Length; i++)
    {
        foreach(char c in listA[i])
        {
            foreach (char d in listB[i]) {
                if (c == d) {
                    contains = true;
                    break;
                }
            }
            if (contains) { break; }
        }
        if (contains == true) {
            Console.WriteLine("YES");
            contains = false;
        } else {
            Console.WriteLine("NO");
        }
    }
}

它通过了大多数测试用例，但在某些情况下它表示运行时间太长（超过 3 秒），所以当有大量输入时。有谁知道我如何优化此代码以使其更快，以便用大输入计算不到 3 秒？所以基本上它打印一个 YES 如果a[i]并且b[i]有一个共同的字符，如果没有，则打印 NO。

标签： c#stringalgorithmsubstring

解决方案

无可避免的事实是，每一对都需要发生一些事情listA[i], listB[i]，这不是问题。但是仔细看看这些嵌套循环：

foreach(char c in listA[i])
{
    foreach (char d in listB[i]) {
        if (c == d) {
            contains = true;
            break;
        }
    }
    if (contains) { break; }
}

你已经发现我们真的只需要找到两个字符串中的一个字母，然后我们就有一个长度为 1 的公共子串（可能有一个更长的公共子串，但这与这个问题无关，因为我们只需要要知道它是否存在 - 你不应该使用“最长的公共子串”算法，这完全是矫枉过正）。这是通过比较每个字符组合来完成的。但是，还有另一种选择：

用字符串 A 中的字符创建一个 HashSet。对于字符串 B 中的每个字符，检查它是否在该 HashSet 中。

操作数从字符串长度的乘积到字符串长度的总和。

推荐阅读