Count Prefix and Suffix Pairs I

You are given a 0-indexed string array words.

Let's define a boolean function isPrefixAndSuffix that takes two strings, str1 and str2:

• isPrefixAndSuffix(str1, str2) returns true if str1 is both a prefix and a suffix of str2, and false otherwise.

For example, isPrefixAndSuffix("aba", "ababa") is true because "aba" is a prefix of "ababa" and also a suffix, but isPrefixAndSuffix("abc", "abcd") is false.

Return an integer denoting the number of index pairs (i, j) such that i < j, and isPrefixAndSuffix(words[i], words[j]) is true.

Example 1:

Input: words = ["a","aba","ababa","aa"]
Output: 4
Explanation: In this example, the counted index pairs are:
i = 0 and j = 1 because isPrefixAndSuffix("a", "aba") is true.
i = 0 and j = 2 because isPrefixAndSuffix("a", "ababa") is true.
i = 0 and j = 3 because isPrefixAndSuffix("a", "aa") is true.
i = 1 and j = 2 because isPrefixAndSuffix("aba", "ababa") is true.
Therefore, the answer is 4.

Example 2:

Input: words = ["pa","papa","ma","mama"]
Output: 2
Explanation: In this example, the counted index pairs are:
i = 0 and j = 1 because isPrefixAndSuffix("pa", "papa") is true.
i = 2 and j = 3 because isPrefixAndSuffix("ma", "mama") is true.
Therefore, the answer is 2.

Example 3:

Input: words = ["abab","ab"]
Output: 0
Explanation: In this example, the only valid index pair is i = 0 and j = 1, and isPrefixAndSuffix("abab", "ab") is false.
Therefore, the answer is 0.

def isPrefixAndSuffix(str1, str2):
    return str2.startswith(str1) and str2.endswith(str1)


def count_prefix_suffix_pairs(words):
    count = 0
    n = len(words)
    for i in range(n):
        for j in range(i + 1, n):
            if isPrefixAndSuffix(words[i], words[j]):
                count += 1
    return count

# Example usage:
words1 = ["a", "aba", "ababa", "aa"]
print(f"Example 1: {count_prefix_suffix_pairs(words1)}")  # Output: 4

words2 = ["pa", "papa", "ma", "mama"]
print(f"Example 2: {count_prefix_suffix_pairs(words2)}")  # Output: 2

words3 = ["abab", "ab"]
print(f"Example 3: {count_prefix_suffix_pairs(words3)}")  # Output: 0

words4 = ["a", "aa", "aaa", "aaaa"]
print(f"Example 4: {count_prefix_suffix_pairs(words4)}") # Output: 6

words5 = ["abc", "def", "ghi"]
print(f"Example 5: {count_prefix_suffix_pairs(words5)}") # Output: 0

words6 = ["ab", "abab", "abcab", "d"]
print(f"Example 6: {count_prefix_suffix_pairs(words6)}") # Output: 1

Naive Approach

The solution iterates through all possible pairs of words (i, j) where i < j. For each pair, it checks if words[i] is both a prefix and a suffix of words[j]. If it is, the counter is incremented. The final count represents the number of pairs that satisfy the condition.

Optimized Approach

The given solution is already relatively optimized for the constraints provided (small word lengths and number of words). Further optimization might involve using more advanced string matching algorithms like the Knuth-Morris-Pratt (KMP) algorithm if the constraints were significantly larger, but given that the maximum word length is only 10 and the maximum number of words is 50, the performance gain from such an optimization would be minimal and would add complexity.

Big O Runtime Analysis

The outer loop iterates n times (where n is the number of words), and the inner loop iterates n - i - 1 times in the worst case, giving us O(n^2) for iterating through all pairs. The isPrefixAndSuffix function uses startswith and endswith, which take O(len(str1)) time in the worst case, where str1 is words[i]. Since the maximum length of any word is 10, this check is effectively constant time. Therefore, the overall time complexity is dominated by the nested loops, resulting in O(n^2).

Big O Space Usage Analysis

The space complexity is O(1) because we are only using a constant amount of extra space to store the count variable and loop indices. We are not using any additional data structures that scale with the input size.

Edge Cases and Handling

1. Empty Input: If the input list words is empty, the loops will not execute, and the function will correctly return 0.
2. Single Element Input: If the input list words contains only one element, the inner loop will not execute, and the function will correctly return 0.
3. Words with Different Lengths: The function handles cases where the words have different lengths correctly because startswith and endswith will return False if the prefix/suffix is longer than the string being checked.
4. Words with Empty Strings: If the list contains empty strings, the function will still work. An empty string is considered both a prefix and suffix of another string only if that other string starts and ends with an empty string, so this case will be handled correctly by the isPrefixAndSuffix function.