Count Prefix and Suffix Pairs I

Easy

Meta

1 view

Topics:

ArraysStrings

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.

Constraints:

1 <= words.length <= 50
1 <= words[i].length <= 10
words[i] consists only of lowercase English letters.

Count Prefix and Suffix Pairs I

Easy

Meta

1 view

Topics:

ArraysStrings

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.

Constraints:

1 <= words.length <= 50
1 <= words[i].length <= 10
words[i] consists only of lowercase English letters.

Solution

Brute Force Solution

The naive approach is to iterate through all possible pairs (i, j) with i < j and check if words[i] is both a prefix and a suffix of words[j].

Code:

def is_prefix_and_suffix(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 is_prefix_and_suffix(words[i], words[j]):
                count += 1
    return count

Time Complexity: O(n^2 * m), where n is the number of words and m is the maximum length of a word. The nested loops contribute O(n^2), and the is_prefix_and_suffix function takes O(m) time for string comparisons.

Space Complexity: O(1), as we use only a constant amount of extra space.

Optimal Solution

While the constraints are small enough that the brute force solution likely passes, we can still consider optimizations. The problem does not appear to have any immediate opportunities to improve beyond O(n^2) with string comparisons. We can make the observation that the string comparisons are relatively fast, and the number of string comparisons will dominate run-time.

Code:

def is_prefix_and_suffix(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 is_prefix_and_suffix(words[i], words[j]):
                count += 1
    return count

Time Complexity: O(n^2 * m), where n is the number of words and m is the maximum length of a word.

Space Complexity: O(1)

Edge Cases

Empty input: If the input array words is empty, the function should return 0. The provided code handles this correctly, as the loops will not execute.
Single word: If the input array contains only one word, there are no pairs to consider, and the function should return 0. The provided code handles this correctly as well.
Words with different lengths: The is_prefix_and_suffix function should handle cases where str1 is longer than str2 gracefully. The startswith and endswith methods in Python handle this by returning False if the substring is longer than the string being checked.
Words are identical: If words are identical (e.g. `[

Solution

Brute Force Solution

The naive approach is to iterate through all possible pairs (i, j) with i < j and check if words[i] is both a prefix and a suffix of words[j].

Code:

def is_prefix_and_suffix(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 is_prefix_and_suffix(words[i], words[j]):
                count += 1
    return count

Space Complexity: O(1), as we use only a constant amount of extra space.

Optimal Solution

Code:

def is_prefix_and_suffix(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 is_prefix_and_suffix(words[i], words[j]):
                count += 1
    return count

Time Complexity: O(n^2 * m), where n is the number of words and m is the maximum length of a word.

Space Complexity: O(1)

Edge Cases

Empty input: If the input array words is empty, the function should return 0. The provided code handles this correctly, as the loops will not execute.
Single word: If the input array contains only one word, there are no pairs to consider, and the function should return 0. The provided code handles this correctly as well.
Words with different lengths: The is_prefix_and_suffix function should handle cases where str1 is longer than str2 gracefully. The startswith and endswith methods in Python handle this by returning False if the substring is longer than the string being checked.
Words are identical: If words are identical (e.g. `[