Finding Pattern Score in Python

Question

I saw this problem in C++ on here and decided to try it in Python, which was much simpler. I've used the same problem blurb as in the link above, so they are consistent. I'm sure my code can be improved.

You are given 3 strings: text, pre_text and post_text. Let L be a substring of text. For each substring L of text, we define pattern_score as follows:

pre_text_pattern_score = highest n, such that first n characters of L are equal to the last n characters of pre_text and occur in the same exact order.

post_text_pattern_score = highest n such that last n characters of L are equal to the first n characters of post_text and occur in the same exact order.

pattern_score = pre_text_pattern_score + post_text_pattern_score. For example, if L = "nothing", pre_text = "bruno", and post_text = "ingenious", then

pre_text_pattern_score of L is 2 because the substring "no" is matched, and

post_text_pattern_score is 3 because the substring "ing" is matched.

pattern_score is 5 = 2 + 3 Your program should find a non-empty substring of text that maximizes pattern_score.

If there is a tie, return the substring with the maximal pre_text_pattern_score.

If multiple answers still have a tied score, return the answer that comes first lexicographically. Complete the definition of function string calculateScore(string text, string prefix,string suffix)

Constraints:

• text, pre_text, and post_text contain only lowercase letters ('a' - 'z')
• 1 <= |text| <= 50
• 1 <= |pre-text| <= 50
• 1 <= |post-text| <= 50 (where |S| denotes the number of characters in string S)

Sample case #1 text: "nothing" prefix: "bruno" suffix: "ingenious" Returns: "nothing" this is "no" from "bruno" and "ing" from "ingenious", so "nothing" is returned.

Sample case #2 text: "ab" prefix: "b" suffix: "a" Returns: "a"

def calculateScore(text, prefixString, suffixString):
    result = {}
    lenText = len(text)

    while lenText > 0:
        for i in range(len(text) + 1 - lenText):
            substring = text[i:i + lenText]
            
            # calc the pre_text_pattern_score
            pre_text_pattern_score = min(len(prefixString), len(substring))

            while pre_text_pattern_score > 0 and substring[:pre_text_pattern_score] != prefixString[-pre_text_pattern_score:]:
                pre_text_pattern_score -= 1
            
            # calc the post_text_pattern_score
            post_text_pattern_score = min(len(suffixString), len(substring))

            while post_text_pattern_score > 0 and substring[-post_text_pattern_score:] != suffixString[:post_text_pattern_score]:
                post_text_pattern_score-= 1
            
            # calculate the pattern_score
            pattern_score = pre_text_pattern_score + post_text_pattern_score

            if not pattern_score in result:
                # resets the dictionary key
                result[pattern_score] = []

            result[pattern_score].append(substring) 

        lenText -= 1 # reduce lenText by 1

    # store the highest key, so we can sort the right item to return   
    maximum_pattern_score = max(result.keys())

    # make sure to sort the lexicographically lowest string of the highest key
    result[maximum_pattern_score].sort()

    # return the lexicographically highest key
    return result[maximum_pattern_score][0]

Answer 1

Code Style

Remember to follow PEP 8 where you can. In particular, you should use snake_case rather than camelCase.

Making your Intentions Clear

Be sure to use comments to explain why your steps are needed rather than just what your code does:

lenText -= 1 # reduce lenText by 1

It is reasonably clear what your code is doing, but you could comment to explain why you're doing this. I'd be tempted to rewrite your substring finding loop as:

# Iterate over all possible substrings of text
for start_index in range(0, len(text)):
    for end_index in range(start_index + 1, len(text) + 1):
        L = text[start_index:end_index]
        # Your logic here

Storing Results

If you preferred, you could save some memory by only storing the patterns that have the highest score we've seen so far.

# Stores the highest seen pattern score so far.
highest_score = 0
# Stores the substrings of text that give highest_score.
highest_substrings = []

You then just need to check if your current score is strictly greater than the highest score seen so far and empty highest_substrings, then if you see a score greater than or equal to highest_score you add that substring to highest_substrings.