# Finding a common prefix

The problem I am trying to solve:

Given a string, split the string into two substrings at every possible point. The rightmost substring is a suffix. The beginning of the string is the prefix. Determine the lengths of the common prefix between each suffix and the original string. Sum and return the lengths of the common prefixes. Return an array where each element 'i' is the sum for the string 'i'. Example:

My Solution:

def commonPrefix(l):

size=len(l)  #Finding number of strings
sumlist=[]  #Initializing list that'll store sums
for i in range(size):
total=0  #Initializing total common prefixes for every string
string=l[i]  #Storing each string in string
strsize=len(string)  #Finding length of each string
for j in range(strsize):
suff=string[j:]   #Calculating every suffix for a string
suffsize=len(suff)  #Finding length of each suffix
common=0   #Size of common prefix for each length
for k in range(suffsize):
if(string[k]==suff[k]):
common=common+1
else:
break   #If characters at equal positions are not equal, break
total=total+common   #Update total for every suffix
sumlist.append(total)   #Add each total in list
return sumlist   #Return list


My solution takes up a lot of time, I need help with optimizing it.

• Welcome to CodeReview! Please indicate the original source of this question - homework or online challenge - ideally with a link. Also, your title needs to indicate what you're actually doing, e.g. "Finding a common prefix". – Reinderien Nov 23 '20 at 14:56

## Second for loop

Your second loop will only iterate once, because string is only 1 character long:

string = l[i]


I think you meant to slice here.

## Incrementing an int

You can use the += operator to increment an integer:

x = 0

for i in range(3):
x += 1


## str.startswith

For the most part, you can use str.startswith to check if the suffix starts with the prefix (other than the case where prefix is ''):

prefix, suffix = 'a', 'abc'

suffix.startswith(prefix)
True


This is a bit more idiomatic than slicing from position i or j to compare with a prefix

## Creating your prefix and suffix

When generating your prefix and suffix, slice once, and you can keep your code down to one loop:

for i in range(len(l)):
# Generate your prefix and suffix here
prefix, suffix = l[:i], l[i:]

# rest of code


## Instead of a counter, use an if statement

For actually tabulating your results, you can use an if statement, paired with the str.startswith logic to cut down on your second loop.

Furthermore, it appears from the example that if the prefix is an empty string, you append the length of the suffix. This can go in the if str.startswith bit because 'anystr'.startswith('') will return True:

results = []

for i in range(len(mystring)):
# Create your prefix and suffix based on slice point
prefix, suffix = mystring[:i], mystring[i:]

# check str.startswith here
if suffix.startswith(prefix):
# You can use a ternary if block in the append to cover the
# empty string case
results.append(len(prefix) if prefix else len(suffix))
else:
results.append(0)


The ternary operator will result in either the left side if the predicate is truthy, otherwise the right side

x = 'a' if True else 'b'

x
'a'

x = 'a' if False else 'b'
x
'b'

x = 'a' if '' else 'b'

x
'b'


Empty strings are falsey.

# Style

## Naming Conventions

Method names should be snake_case:

def some_method_name():
# do things


## Spacing

There should be a space between a name, the equals sign, and a value:

# instead of this
some_value=3

# do this
some_value = 3


The exception to this is with keyword arguments in a function

def f(key='value'):
return None

# No extra spaces here
f(key=1)


string is the name of a module, so watch out for cases where you might acidentally name a variable something that you may import (or users of your code might import). Not a huge deal in this case, but certainly something to watch out for. Note that this accounts mostly for common modules and functions, both built-in and 3rd party like string, pandas, math, sum, etc.
You can do with a list comprehension and the string find function
def common_prefix(l):