Find the common parent path in the list of files and directories

Question

I have a list of files and directories List<string> pathes . Now I would like to calculate the deepest common branch, each of which shares with each other.

We can assume that they all have a common path, but this is unknown at the beginning.

Let's say I have the following three entries:

• C: /Hello/World/This/Is/An/Example/Bla.cs
• C: / Hello / World / This / Is / Not / Ap / Example /
• C: / Hello / Earth / Bla / Bla / Bla

This should get the result: C: / Hello /, since Earth destroys this "chain" of subdirectories.

Second example:

• C: /Hello/World/This/Is/An/Example/Bla.cs
• C: / Hello / World / This / Is / Not / Ap / Example /

-> C: / Hello / World / This / Is /

What will you do? I tried to use string.split (@ "/") and start from the first line and check if each part of this array is contained in other lines. However, this will be a very expensive call as I repeat (list_of_entries) ^ list_of_entries. Is there a better solution?

My current attempt will be similar to the following (C # + LINQ):

  public string CalculateCommonPath(IEnumerable<string> paths) { int minSlash = int.MaxValue; string minPath = null; foreach (var path in paths) { int splits = path.Split('\\').Count(); if (minSlash > splits) { minSlash = splits; minPath = path; } } if (minPath != null) { string[] splits = minPath.Split('\\'); for (int i = 0; i < minSlash; i++) { if (paths.Any(x => !x.StartsWith(splits[i]))) { return i >= 0 ? splits.Take(i).ToString() : ""; } } } return minPath; } 

Answer 1

The function to get the longest common prefix might look like this:

 public static string GetLongestCommonPrefix(string[] s) { int k = s[0].Length; for (int i = 1; i < s.Length; i++) { k = Math.Min(k, s[i].Length); for (int j = 0; j < k; j++) if (s[i][j] != s[0][j]) { k = j; break; } } return s[0].Substring(0, k); } 

Then you may need to cut the prefix in your right hand. For example. we want to return c:/dir instead of c:/dir/file for

 c:/dir/file1 c:/dir/file2 

You can also normalize paths before processing. See Normalize Directory Names in C # .

Answer 2

I do not know if this is the best solution (maybe not), but it is very easy to implement.

• Sort alphabetically
• compares the first entry in this sorted list with the last in this list, character by character and ends when you find the difference (the value to the end is the longest common substring of both of these lines)

Script example

Code example:

 List<string> paths = new List<string>(); paths.Add(@"C:/Hello/World/This/Is/An/Example/Bla.cs"); paths.Add(@"C:/Hello/World/This/Is/Not/An/Example/"); paths.Add(@"C:/Hello/Earth/Bla/Bla/Bla"); List<string> sortedPaths = paths.OrderBy(s => s).ToList(); Console.WriteLine("Most common path here: {0}", sharedSubstring(sortedPaths[0], sortedPaths[sortedPaths.Count - 1])); 

And this function, of course:

 public static string sharedSubstring(string string1, string string2) { string ret = string.Empty; int index = 1; while (string1.Substring(0, index) == string2.Substring(0, index)) { ret = string1.Substring(0, index); index++; } return ret; } // returns an empty string if no common characters where found 

Answer 3

I would iterate over each character in the first path, comparing it with every character in every path (except the first) in the path collection:

 public string FindCommonPath(List<string> paths) { string firstPath = paths[0]; bool same = true; int i = 0; string commonPath = string.Empty; while (same && i < firstPath.Length) { for (int p = 1; p < paths.Count && same; p++) { same = firstPath[i] == paths[p][i]; } if (same) { commonPath += firstPath[i]; } i++; } return commonPath; } 

You can iterate through the list first to find the shortest path and possibly improve it a bit.

Answer 4

First sort the list using the paths to check. Then you can separate and compare the first and last elements - if they are the same, proceed to the next dimension until you find the difference.

So, you just need to sort once, and then check the two elements.