0
\$\begingroup\$

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:

Example table

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.

\$\endgroup\$
1
  • 3
    \$\begingroup\$ 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". \$\endgroup\$ – Reinderien Nov 23 '20 at 14:56
2
\$\begingroup\$

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 = []

# Start your loop
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)

Be careful about name shadowing

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.

\$\endgroup\$
0
\$\begingroup\$

You can do with a list comprehension and the string find function

def common_prefix(l):
    return [
        len(l[:i]) or len(l) if l[i:].find(l[:i]) == 0 else 0
        for i in range(len(l))
    ]

Your code did not throw a good solution for the string given though

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.