Given n directory paths, we need to write a program to find longest common directory path.
Examples:
Input : 3
"/home/User/Desktop/gfg/test"
"/home/User/Desktop/gfg/file"
"/home/User/Desktop/neveropen/folders"
Output : Longest Common Path is /home/User/Desktop!
Input : 4
"/home/User/Desktop/gfg/test",
"/home/User/Desktop/gfg/file",
"/home/User/Desktop/gfg/folders",
"/home/User/Desktop/gfg/folders"
Output : Longest Common Path is /home/User/Desktop/gfg!
In the function LongestCommonPath() there are two main variables used which are “CommonCharacters” for storing the length of common characters and “CommonString” for storing the longest string of paths so that we get our longest common path.
CommonCharacter variable gets updated in each iteration depending upon the length of common path appearing in the input paths.
Lastly, we get the length of common path string after the iteration. Then, we get our common path by the substring till the separator ‘/’ as if we don’t do this then we get the longest common string among the paths, which should not be our result .
Below is the implementation of the above approach .
CPP
// CPP program for longest common path#include <bits/stdc++.h>using namespace std;string LongestCommonPath(const vector<string>& input_directory, char separator){ vector<string>::const_iterator iter; // stores the length of common characters // and initialized with the length of // first string . int CommonCharacters = input_directory[0].length(); // stores the common string and initialized // with the first string . string CommonString = input_directory[0]; for (iter = input_directory.begin() + 1; iter != input_directory.end(); iter++) { // finding the two pointers through the mismatch() // function which is 'mismatch at first string' and // 'mismatch at the other string ' pair<string::const_iterator, string::const_iterator> p = mismatch(CommonString.begin(), CommonString.end(), iter->begin()); // As the first mismatch string pointer points to the mismatch // present in the "CommonString" so "( p.first-CommonString.begin())" // determines the common characters in each iteration . if ((p.first - CommonString.begin()) < CommonCharacters) { // If the expression is smaller than commonCharacters // then we will update the commonCharacters because // this states that common path is smaller than the // string commonCharacters we have evaluated till . CommonCharacters = p.first - CommonString.begin(); } // Updating CommonString variable // so that in this maximum length // string is stored . if (*iter > CommonString) CommonString = *iter; } // In 'found' variable we store the index of '/' in // the length of common characters in CommonString int found; for (int i = CommonCharacters; i >= 0; --i) { if (CommonString[i] == '/') { found = i; break; } } // The substring from index 0 to index of // separator is the longest common substring return CommonString.substr(0, found);}int main(){ int n = 4; string input_directory[4] = { "/home/User/Desktop/gfg/test", "/home/User/Desktop/gfg/file", "/home/User/Desktop/gfg/folders", "/home/User/Desktop/gfg/folders" }; vector<string> input(input_directory, input_directory + n); cout << "Longest Common Path is " << LongestCommonPath(input, '/') << "!\n"; return 0;} |
Java
import java.util.*;public class GFG { public static String LongestCommonPath(final List<String> input_directory, final char separator) { // stores the length of common characters // and initialized with the length of // first string . int CommonCharacters = input_directory.get(0).length(); // stores the common string and initialized // with the first string . String CommonString = input_directory.get(0); for (int i = 1; i < input_directory.size(); i++) { String iter = input_directory.get(i); int n = Math.min(CommonString.length(), iter.length()); int j = 0; while (j < n && CommonString.charAt(j) == iter.charAt(j)) { j++; } if (j < CommonCharacters) { CommonCharacters = j; } if (iter.compareTo(CommonString) > 0) { CommonString = iter; } } // In 'found' variable we store the index of '/' in // the length of common characters in CommonString int found = -1; for (int i = CommonCharacters; i >= 0; --i) { if (CommonString.charAt(i) == separator) { found = i; break; } } // The substring from index 0 to index of // separator is the longest common substring return CommonString.substring(0, found); } public static void main(String[] args) { String[] input_directory = { "/home/User/Desktop/gfg/test", "/home/User/Desktop/gfg/file", "/home/User/Desktop/gfg/folders", "/home/User/Desktop/gfg/folders" }; List<String> input = new ArrayList<>(Arrays.asList(input_directory)); System.out.println("Longest Common Path is " + LongestCommonPath(input, '/') + "!"); }} |
Python3
# Python program for the above approachfrom typing import Listdef LongestCommonPath(input_directory: List[str], separator: str) -> str: # stores the length of common characters # and initialized with the length of # first string. CommonCharacters = len(input_directory[0]) # stores the common string and initialized # with the first string. CommonString = input_directory[0] for i in range(1, len(input_directory)): # finding the two pointers through the mismatch() # function which is 'mismatch at first string' and # 'mismatch at the other string ' p = mismatch(CommonString, input_directory[i]) # As the first mismatch string pointer points to the mismatch # present in the "CommonString" so "( p[0])" # determines the common characters in each iteration. if p[0] < CommonCharacters: # If the expression is smaller than CommonCharacters # then we will update the CommonCharacters because # this states that common path is smaller than the # string CommonCharacters we have evaluated till. CommonCharacters = p[0] # Updating CommonString variable # so that in this maximum length # string is stored. if input_directory[i] > CommonString: CommonString = input_directory[i] # In 'found' variable we store the index of separator in # the length of common characters in CommonString found = CommonString.rfind(separator, 0, CommonCharacters) # The substring from index 0 to index of separator # is the longest common substring return CommonString[:found]def mismatch(s1, s2): n = min(len(s1), len(s2)) for i in range(n): if s1[i] != s2[i]: return (i, s1[i], s2[i]) if len(s1) != len(s2): return (n, "", "") return (-1, "", "")if __name__ == '__main__': n = 4 input_directory = [ "/home/User/Desktop/gfg/test", "/home/User/Desktop/gfg/file", "/home/User/Desktop/gfg/folders", "/home/User/Desktop/gfg/folders" ] print("Longest Common Path is", LongestCommonPath(input_directory, '/'), "!") # This code is contributed by codebraxnzt |
Javascript
// Javascript program for the above approachfunction LongestCommonPath(input_directory, separator) {// stores the length of common characters// and initialized with the length of// first string.let CommonCharacters = input_directory[0].length;// stores the common string and initialized// with the first string.let CommonString = input_directory[0];for (let i = 1; i < input_directory.length; i++) { // finding the two pointers through the mismatch() // function which is 'mismatch at first string' and // 'mismatch at the other string ' let p = mismatch(CommonString, input_directory[i]); // As the first mismatch string pointer points to the mismatch // present in the "CommonString" so "( p[0])" // determines the common characters in each iteration. if (p[0] < CommonCharacters) { // If the expression is smaller than CommonCharacters // then we will update the CommonCharacters because // this states that common path is smaller than the // string CommonCharacters we have evaluated till. CommonCharacters = p[0]; } // Updating CommonString variable // so that in this maximum length // string is stored. if (input_directory[i] > CommonString) { CommonString = input_directory[i]; }}// In 'found' variable we store the index of separator in// the length of common characters in CommonStringlet found = CommonString.lastIndexOf(separator, CommonCharacters);// The substring from index 0 to index of separator// is the longest common substringreturn CommonString.substring(0, found);}function mismatch(s1, s2) {let n = Math.min(s1.length, s2.length);for (let i = 0; i < n; i++) {if (s1.charAt(i) != s2.charAt(i)) {return [i, s1.charAt(i), s2.charAt(i)];}}if (s1.length != s2.length) {return [n, "", ""];}return [-1, "", ""];}let input_directory = ["/home/User/Desktop/gfg/test","/home/User/Desktop/gfg/file","/home/User/Desktop/gfg/folders","/home/User/Desktop/gfg/folders"];console.log("Longest Common Path is", LongestCommonPath(input_directory, '/'), "!"); |
Output
Longest Common Path is /home/User/Desktop/gfg!
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
