c# - 将两个列表相交并返回与原始第一个字符串值的保留顺序的相似度

Question

我面临一个问题，我什至不知道在 Google/Stack Overflow 中搜索什么。因此，如果您觉得需要进一步解释和问题，请发表评论。

基本上我想将两个列表相交并返回与原始第一个字符串值的保留顺序的相似度。

例子:

我有两个字符串，我将它们转换为 CharArray。我想将这两个数组相交并返回相似的值，包括/与第一个字符串 (s1) 的顺序。

---

如您所见，第一个字符串包含 E15(按特定顺序)，第二个字符串也是如此。

因此这两个字符串将返回:{ 'E', '1', '5' }

string s1 = "E15QD(A)";
string s2 = "NHE15H";

我面临的问题是，如果我将“s2”替换为:

string s2 = "NQE18H" // Will return {'Q', 'E', '1' }

我的操作将返回:{'Q', 'E', '1' }

结果应该是:{'E', '1'}因为Q不跟在字母1

目前我的操作不是最大的努力，因为我不知道在.NET中使用哪些方法能够做到这一点。

当前代码:

List<char> cA1 = s1.ToList();
List<char> cA2 = s2.ToList();

var result = cA1.Where(x => cA2.Contains(x)).ToList();

请随时帮助我，可以接受正确方向的指示以及完整的解决方案。

Answer 1

这是一个 "longest common substring"问题。

您可以使用此扩展来延迟获取所有子字符串:

public static class StringExtensions
{
    public static IEnumerable<string> GetSubstrings(this string str)
    {
        if (string.IsNullOrEmpty(str))
            throw new ArgumentException("str must not be null or empty", "str");

        for (int c = 0; c < str.Length - 1; c++)
        {
            for (int cc = 1; c + cc <= str.Length; cc++)
            {
                yield return str.Substring(c, cc);
            }
        }
    }
}

然后使用此 LINQ 查询变得简单易读:

string longestIntersection = "E15QD(A)".GetSubstrings()
    .Intersect("NQE18H".GetSubstrings())
    .OrderByDescending(s => s.Length)
    .FirstOrDefault();  // E1

Enumerable.Intersect也非常有效，因为它使用的是集合。一个注意事项:如果两个字符串中的一个比另一个大，那么首先使用它会更有效(就内存而言):

longString.GetSubstrings().Intersect(shortString.GetSubstrings())