能否找出字符串列表中的共同部分？

Question

我正在研究在字符串列表中找到共同的字符串部分。如果我们采用样本数据集

private readonly List<string> Xpath = new List<string>()
{   
    "BODY>MAIN:nth-of-type(1)>DIV>SECTION>DIV>SECTION>DIV>DIV:nth-of-type(1)>DIV>DIV:nth-of-type(3)>DIV>ARTICLE>DIV>DIV>DIV>SECTION:nth-of-type(1)>H2:nth-of-type(1)",
    "BODY>MAIN:nth-of-type(1)>DIV>SECTION>DIV>SECTION>DIV>DIV:nth-of-type(1)>DIV>DIV:nth-of-type(3)>DIV>ARTICLE>DIV>DIV>DIV>SECTION:nth-of-type(2)>H2:nth-of-type(1)",
    "BODY>MAIN:nth-of-type(1)>DIV>SECTION>DIV>SECTION>DIV>DIV:nth-of-type(1)>DIV>DIV:nth-of-type(3)>DIV>ARTICLE>DIV>DIV>DIV>SECTION:nth-of-type(3)>H2:nth-of-type(1)",
    "BODY>MAIN:nth-of-type(1)>DIV>SECTION>DIV>SECTION>DIV>DIV:nth-of-type(1)>DIV>DIV:nth-of-type(3)>DIV>ARTICLE>DIV>DIV>DIV>SECTION:nth-of-type(4)>H2:nth-of-type(1)",
    "BODY>MAIN:nth-of-type(1)>DIV>SECTION>DIV>SECTION>DIV>DIV:nth-of-type(1)>DIV>DIV:nth-of-type(3)>DIV>ARTICLE>DIV>DIV>DIV>SECTION:nth-of-type(5)>H2:nth-of-type(1)",
    "BODY>MAIN:nth-of-type(1)>DIV>SECTION>DIV>SECTION>DIV>DIV:nth-of-type(1)>DIV>DIV:nth-of-type(3)>DIV>ARTICLE>DIV>DIV>DIV>SECTION:nth-of-type(6)>H2:nth-of-type(1)",
    "BODY>MAIN:nth-of-type(1)>DIV>SECTION>DIV>SECTION>DIV>DIV:nth-of-type(1)>DIV>DIV:nth-of-type(3)>DIV>ARTICLE>DIV>DIV>DIV>SECTION:nth-of-type(7)>H2:nth-of-type(1)",
    "BODY>MAIN:nth-of-type(1)>DIV>SECTION>DIV>SECTION>DIV>DIV:nth-of-type(1)>DIV>DIV:nth-of-type(3)>DIV>ARTICLE>DIV>DIV>DIV>SECTION:nth-of-type(8)>H2:nth-of-type(1)",
    "BODY>MAIN:nth-of-type(1)>DIV>SECTION>DIV>SECTION>DIV>DIV:nth-of-type(1)>DIV>DIV:nth-of-type(3)>DIV>ARTICLE>DIV>DIV>DIV>SECTION:nth-of-type(9)>H2:nth-of-type(1)"
};

根据这个，我希望找出与哪些孩子相似的数据是一组Xpath列表。

我应该能够编程来告诉：

BODY>MAIN:nth-of-type(1)>DIV>SECTION>DIV>SECTION>DIV>DIV:nth-of-type(1)>DIV>DIV:nth-of-type(3)>DIV>ARTICLE>DIV>DIV>DIV

为了达到这个目的，我做的是像这样。我使用>将每个项分开，然后为每个原始数据集创建一个项目列表。

接着使用这个列表，找出其中唯一的项目。

private IEnumerable<T> GetCommonItems<T>(IEnumerable<T>[] lists)
{
    HashSet<T> hs = new HashSet<T>(lists.First());
    for (int i = 1; i < lists.Length; i++)
    {
        hs.IntersectWith(lists[i]);
    }
    return hs;
}

能够找出唯一的值并重新创建数据集。但是，如果数据集中存在类似于“Div”在两个地方的情况，并且它也在每个原始数据集中，那么这种方法将只选择一个“Div”。

因此，最终可能会得到以下内容：

BODY>MAIN:nth-of-type(1)>DIV>SECTION

但是我需要的是：

BODY>MAIN:nth-of-type(1)>DIV>SECTION>DIV>SECTION>DIV>DIV:nth-of-type(1)>DIV>DIV:nth-of- type(3)>DIV>ARTICLE>DIV>DIV>DIV

- ish1104

---

https://leetcode.com/problems/longest-common-prefix/discuss/6924/Sorted-the-array-Java-solution-2-ms - ASh

Answer 1

免责声明：这不是最有效的解决方案，但它可以工作 :)

• 首先按>字符拆分第一个路径
• 对所有路径执行相同操作

char separator = '>';
IEnumerable<string> firstPathChunks = Xpath[0].Split(separator);
var chunks = Xpath.Select(path => path.Split(separator).ToList()).ToArray();

• 遍历firstPathChunks
• 遍历chunks
• 如果有匹配的内容，则删除第一个元素
• 如果所有的第一个元素都被删除了，则将匹配的前缀添加到sb中

void Process(StringBuilder sb)
{
    foreach (var pathChunk in firstPathChunks)
    {
        foreach (var chunk in chunks)
        {
            if (chunk[0] != pathChunk)
            {
                return;
            }
            chunk.RemoveAt(0);
        }
        sb.Append(pathChunk); 
        sb.Append(separator);
    }
}

示例用法

var sb = new StringBuilder();
Process(sb);
Console.WriteLine(sb.ToString());

---

输出

BODY>MAIN:nth-of-type(1)>DIV>SECTION>DIV>SECTION>DIV>DIV:nth-of-type(1)>DIV>DIV:nth-of-type(3)>DIV>ARTICLE>DIV>DIV>DIV>

- Peter Csala

Answer 2

使用分隔符>解析字符串是一个好主意。不要创建唯一项列表，而应该创建包含在字符串中的所有项的列表，这将导致

{
    "BODY",
    "MAIN:nth-of-type(1)",
    "DIV",
    "SECTTION",
    "DIV",
    ...
}

对于您的XPath列表的第一个条目。

这样，您将创建一个包含XPath列表每个条目的每个元素的“List>”。然后，您可以比较内部列表的所有第一个元素。如果它们相等，请将该元素的值保存到输出中，并继续处理所有第二个元素，直到找到在所有外部列表中不相等的元素。

编辑： 在使用“>”分隔符分隔列表之后，这可能看起来像这样：

    List<List<string>> XPathElementsLists;
    List<string> resultElements = new List<string>();
    string result;

    XPathElementsLists = ParseElementsFormXPath(XPath);

    for (int i = 0; i < XPathElementsLists[0].Count; i++)
    {
        bool isEqual = true;
        string compareElemment = XPathElementsLists[0][i];
        foreach (List<string> element in XPathElementsLists)
        {
            if (!String.Equals(compareElemment, element))
            {
                isEqual = false;
                break;
            }
        }
        if (!isEqual)
        {
            break;
        }
        resultElements.Add(compareElemment);
    }

    result = String.Join(">", resultElements.ToArray());

- Felix