在字符串数组中找到最长的子串,并将其从数组中的所有元素中删除 [英] Find longest substring in an array of strings and remove it from all the elements in the array
问题描述
例如我有这个数组(大小是可变的):
I have this array, for example (the size is variable):
x = ["10111", "10122", "10250", "10113"]
我需要找到最长的字符串,它是每个数组元素的子字符串(在本例中为10")(它不必是字符串的前缀).我必须从所有字符串中删除它.此示例的输出将是:
I need to find the longest string that is a substring of each array element ("10" in this case) (it need not to be a prefix of the strings). I have to remove it from all the strings. The output for this example would be:
x=["111","222","250","113"] //common value = "10"
推荐答案
这个扩展找到最长最常见的子字符串.请注意,"1"
也比 "10"
更频繁地包含在每个字符串中.(仅限 C#):
This extension finds the longest most common substring(s). Note that "1"
is also contained in every string even more often than "10"
. (C# only):
public static class StringExtensions
{
public static IEnumerable<string> GetMostCommonSubstrings(this IList<string> strings)
{
if (strings == null)
throw new ArgumentNullException("strings");
if (!strings.Any() || strings.Any(s => string.IsNullOrEmpty(s)))
throw new ArgumentException("None string must be empty", "strings");
var allSubstrings = new List<List<string>>();
for (int i = 0; i < strings.Count; i++)
{
var substrings = new List<string>();
string str = strings[i];
for (int c = 0; c < str.Length - 1; c++)
{
for (int cc = 1; c + cc <= str.Length; cc++)
{
string substr = str.Substring(c, cc);
if (allSubstrings.Count < 1 || allSubstrings.Last().Contains(substr))
substrings.Add(substr);
}
}
allSubstrings.Add(substrings);
}
if (allSubstrings.Last().Any())
{
var mostCommon = allSubstrings.Last()
.GroupBy(str => str)
.OrderByDescending(g => g.Key.Length)
.ThenByDescending(g => g.Count())
.Select(g => g.Key);
return mostCommon;
}
return Enumerable.Empty<string>();
}
}
现在很简单:
string[] x = new[] { "10111", "10122", "10250", "10113" };
string mostCommonSubstring = x.GetMostCommonSubstrings().FirstOrDefault();
if (mostCommonSubstring != null)
{
for (int i = 0; i < x.Length; i++)
x[i] = x[i].Replace(mostCommonSubstring, "");
}
Console.Write(string.Join(", ", x));
输出:
111, 122, 250, 113
编辑:如果您只想找到最长公共子串而不考虑出现频率,您可以使用 HashSet
:
Edit: If you just want to find the longest common substring without taking the frequency of occurrence into account you can use this optimzed approach(O(n) operation) using a HashSet<string>
:
public static string GetLongestCommonSubstring(this IList<string> strings)
{
if (strings == null)
throw new ArgumentNullException("strings");
if (!strings.Any() || strings.Any(s => string.IsNullOrEmpty(s)))
throw new ArgumentException("None string must be empty", "strings");
var commonSubstrings = new HashSet<string>(strings[0].GetSubstrings());
foreach (string str in strings.Skip(1))
{
commonSubstrings.IntersectWith(str.GetSubstrings());
if (commonSubstrings.Count == 0)
return null;
}
return commonSubstrings.OrderByDescending(s => s.Length).First();
}
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);
}
}
}
以这种方式使用它:
string[] x = new[] { "101133110", "101233210", "102533010", "101331310" };
string longestCommon = x.GetLongestCommonSubstring(); // "10"
这篇关于在字符串数组中找到最长的子串,并将其从数组中的所有元素中删除的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!