Given a set of strings, write a Python program to determine common prefix from a set of strings. Given below are a few methods to solve the above task.
Method #1: Using Naive Approach
Python3
# Python code to demonstrate # to find common prefix# from set of strings# Initialising stringini_strlist = ['akshat', 'akash', 'akshay', 'akshita']# Finding common prefix using Naive Approachres = ''prefix = ini_strlist[0]for string in ini_strlist[1:]: while string[:len(prefix)] != prefix and prefix: prefix = prefix[:len(prefix)-1] if not prefix: breakres = prefix# Printing resultprint("Resultant prefix", str(res)) |
Resultant prefix ak
Method #2: Using itertools.takewhile and zip
Python3
# Python code to demonstrate # to find common prefix# from set of stringsfrom itertools import takewhile# Initialising stringini_strlist = ['akshat', 'akash', 'akshay', 'akshita']# Finding common prefix using Naive Approachres = ''.join(c[0] for c in takewhile(lambda x: all(x[0] == y for y in x), zip(*ini_strlist)))# Printing resultprint("Resultant prefix", str(res)) |
Resultant prefix ak
Complexity Analysis:
In both the solutions time and space complexity are the same:
Time Complexity: O(n2)
Auxiliary Space: O(n)
Method #3: Using the Python built-in function os.path.commonprefix()
This method uses the os.path.commonprefix() built-in function in the python os library to find the common prefix of a set of strings.
Python3
import os# Initializing the list of stringsini_strlist = ['akshat', 'akash', 'akshay', 'akshita']# Using the Python built-in function os.path.commonprefix() to find the common prefix of the list of stringsprefix = os.path.commonprefix(ini_strlist)# Printing the resultprint("Resultant prefix", prefix)#This code is contributed by Edula Vinay Kumar Reddy |
Resultant prefix ak
Time Complexity: O(n*l) where n is the number of strings in the set and l is the length of the longest string.
Auxiliary Space: O(n)
The above code import the os library and then use the os.path.commonprefix(ini_strlist) function on the set of strings. The function return the common prefix among all the string in set.
