Count Prefix and Suffix Pairs I

EASY

Description

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.

Approaches

Checkout 2 different approaches to solve Count Prefix and Suffix Pairs I. Click on different approaches to view the approach and algorithm in detail.

Brute-Force Iteration

The most straightforward approach is to iterate through all possible pairs of indices (i, j) where i < j and check if words[i] is both a prefix and a suffix of words[j]. This involves nested loops and direct string comparisons.

Algorithm

Initialize a counter variable count to zero.
Use two nested loops to generate all unique pairs of indices (i, j) such that i < j. The outer loop runs from i = 0 to words.length - 1, and the inner loop runs from j = i + 1 to words.length - 1.
Inside the inner loop, for each pair of strings words[i] and words[j], perform the required check.
Use built-in string functions to check the conditions: words[j].startsWith(words[i]) for the prefix condition and words[j].endsWith(words[i]) for the suffix condition.
If both functions return true, it means we have found a valid pair, so we increment our count.
After the loops complete, count holds the total number of such pairs, which is then returned.

We initialize a counter variable count to zero. We use two nested loops to generate all unique pairs of indices (i, j) such that i is less than j. The outer loop runs from i = 0 to words.length - 1, and the inner loop runs from j = i + 1 to words.length - 1. Inside the inner loop, for each pair of strings words[i] and words[j], we perform the required check. A simple optimization is to first check if the length of words[i] is greater than the length of words[j]. If it is, words[i] cannot be a prefix or suffix, so we can skip to the next pair. We then use built-in string functions to check the conditions. words[j].startsWith(words[i]) checks for the prefix condition, and words[j].endsWith(words[i]) checks for the suffix condition. If both functions return true, it means we have found a valid pair, so we increment our count. After the loops complete, count holds the total number of such pairs.

class Solution {
    public int countPrefixAndSuffixPairs(String[] words) {
        int count = 0;
        int n = words.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                String str1 = words[i];
                String str2 = words[j];
                if (str2.startsWith(str1) && str2.endsWith(str1)) {
                    count++;
                }
            }
        }
        return count;
    }
}

Complexity Analysis

Time Complexity: O(N^2 * L), where `N` is the number of words and `L` is the maximum length of a word. We have two nested loops giving `O(N^2)` pairs. For each pair, `startsWith` and `endsWith` operations take up to `O(L)` time.Space Complexity: O(1), as we only use a constant amount of extra space for the counter and loop variables.

Pros and Cons

Pros:

Simple to understand and implement.
Very low memory usage.
Sufficiently fast for the given problem constraints.

Cons:

Less efficient than other possible solutions. The time complexity is quadratic in the number of words, which would be too slow for larger inputs.

Code Solutions

Checking out 3 solutions in different languages for Count Prefix and Suffix Pairs I. Click on different languages to view the code.

Video Solution

Watch the video walkthrough for Count Prefix and Suffix Pairs I

Patterns:

String MatchingRolling HashHash Function

Data Structures:

ArrayStringTrie

Companies:

Capital One |Autodesk |