Hi everyone,
I recently solved a LeetCode problem involving counting pairs of words where one is both a prefix and a suffix of the other. Here's the breakdown of my brute force solution:
Intuition:
A prefix appears at the start of a string, and a suffix at the end. For example, in "ababa", "aba" is both a prefix and suffix. To find such pairs:
- Compare every pair of words.
- Check if one word is a prefix and a suffix of the other.
- Increment the count for valid pairs.
- This approach is simple but can get inefficient for larger inputs.
Algorithm:
- Loop through all pairs of words (i, j) where j > i.
- For each pair:
- Skip if word1 (shorter word) is longer than word2.
- Check if word2 starts and ends with word1 (using startsWith and endsWith).
3.Increment a counter for valid pairs.
- Return the count.
Implementation:
Hereβs the Python code:
`class Solution:
def countPrefixSuffixPairs(self, words: List[str]) -> int:
n = len(words)
count = 0
# Step 1: Iterate through each pair of words
for i in range(n):
for j in range(i + 1, n):
str1 = words[i]
str2 = words[j]
# Step 2: Skip if the first string is larger than the second
if len(str1) > len(str2):
continue
# Step 3: Check if str1 is both the prefix and suffix of str2
if str2.startswith(str1) and str2.endswith(str1):
count += 1
# Step 4: Return the total count of prefix-suffix pairs
return count
`
Testcases and Results:
The Testcases and result of the given code are given below.
Complexity Analysis
Time Complexity:
π(n2β
π), where π is the number of words, and π is the average word length.
Space Complexity:
π(1) as no extra space is used beyond counters and loop variables.
This brute force approach works well for small inputs but is inefficient for larger datasets. I'd love to hear your thoughts or optimizations! π
