Instead of using functions like startswith or endswith, I used an approach to verify both the prefix and suffix conditions manually.
The first step was to define the isPrefixAndSuffix function. This function checks whether one string is both a prefix and a suffix of another. To do this, the function compares the characters of str1 with the corresponding characters in str2. For the prefix condition, the function iterates over the characters of str1 and verifies that they match the corresponding characters in str2 starting from the beginning. Similarly, for the suffix condition, it iterates over the characters of str1 and ensures they match the corresponding characters in str2 starting from the end. If both conditions are satisfied, the function returns True; otherwise, it returns False.
The second step was to count all valid pairs of indices (i, j) where ( i < j). For such pair, the program checks if isPrefixAndSuffix(words[i], words[j]) evaluates to True. If it does, a counter is incremented to track the number of valid pairs.
class Solution:
def countPrefixSuffixPairs(self, words: List[str]) -> int:
def isPrefixAndSuffix(str1: str, str2: str) -> bool:
for i in range(len(str1)):
if i >= len(str2) or str1[i] != str2[i]:
return False
for i in range(len(str1)):
if i >= len(str2) or str1[i] != str2[len(str2) - len(str1) + i]:
return False
return True
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- Time: O(n^2.k) where n is the number of strings and k is the maximum length of the strings.
- Space: O(1).
