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 thati < j, andisPrefixAndSuffix(words[i], words[j])istrue.
Input: words =["a","aba","ababa","aa"]Output: 4Explanation: In this example, the counted index pairs are:i =0 and j =1 because isPrefixAndSuffix("a","aba")istrue.i =0 and j =2 because isPrefixAndSuffix("a","ababa")istrue.i =0 and j =3 because isPrefixAndSuffix("a","aa")istrue.i =1 and j =2 because isPrefixAndSuffix("aba","ababa")istrue.Therefore, the answer is4.
Example 2:
1
2
3
4
5
6
Input: words =["pa","papa","ma","mama"]Output: 2Explanation: In this example, the counted index pairs are:i =0 and j =1 because isPrefixAndSuffix("pa","papa")istrue.i =2 and j =3 because isPrefixAndSuffix("ma","mama")istrue.Therefore, the answer is2.
Example 3:
1
2
3
4
Input: words =["abab","ab"]Output: 0Explanation: In this example, the only valid index pair is i =0 and j =1, and isPrefixAndSuffix("abab","ab")isfalse.Therefore, the answer is0.
classSolution {
publicintcountPrefixSuffixPairs(String[] words) {
int ans = 0;
for (int i = 0; i < words.length; i++) {
for (int j = i + 1; j < words.length; j++) {
if (isPrefixAndSuffix(words[i], words[j])) {
ans++;
}
}
}
return ans;
}
privatebooleanisPrefixAndSuffix(String str1, String str2) {
return str2.startsWith(str1) && str2.endsWith(str1);
}
}
1
2
3
4
5
6
7
8
9
10
11
classSolution:
defcountPrefixSuffixPairs(self, words: List[str]) -> int:
ans: int =0for i in range(len(words)):
for j in range(i +1, len(words)):
if self.isPrefixAndSuffix(words[i], words[j]):
ans +=1return ans
defisPrefixAndSuffix(self, str1: str, str2: str) -> bool:
return str2.startswith(str1) and str2.endswith(str1)
⏰ Time complexity: O(n^2 * l), where n is the length of the words array and l is average length of words, because of the nested loop and starts with and ends with take O(l) time where l is length of prefix and suffix, and is proportional to average length of word..