题目描述
给你一个下标从 0 开始的字符串数组 words
。
定义一个 布尔 函数 isPrefixAndSuffix
,它接受两个字符串参数 str1
和 str2
:
- 当
str1
同时是str2
的前缀(prefix)和后缀(suffix)时,isPrefixAndSuffix(str1, str2)
返回true
,否则返回false
。
例如,isPrefixAndSuffix("aba", "ababa")
返回 true
,因为 "aba"
既是 "ababa"
的前缀,也是 "ababa"
的后缀,但是 isPrefixAndSuffix("abc", "abcd")
返回 false
。
以整数形式,返回满足 i < j
且 isPrefixAndSuffix(words[i], words[j])
为 true
的下标对 (i, j)
的 数量。
样例
输入:words = ["a","aba","ababa","aa"]
输出:4
解释:在本示例中,计数的下标对包括:
i = 0 且 j = 1,因为 isPrefixAndSuffix("a", "aba") 为 true。
i = 0 且 j = 2,因为 isPrefixAndSuffix("a", "ababa") 为 true。
i = 0 且 j = 3,因为 isPrefixAndSuffix("a", "aa") 为 true。
i = 1 且 j = 2,因为 isPrefixAndSuffix("aba", "ababa") 为 true。
因此,答案是 4。
输入:words = ["pa","papa","ma","mama"]
输出:2
解释:在本示例中,计数的下标对包括:
i = 0 且 j = 1,因为 isPrefixAndSuffix("pa", "papa") 为 true。
i = 2 且 j = 3,因为 isPrefixAndSuffix("ma", "mama") 为 true。
因此,答案是 2。
输入:words = ["abab","ab"]
输出:0
解释:在本示例中,唯一有效的下标对是 i = 0 且 j = 1,
但是 isPrefixAndSuffix("abab", "ab") 为 false。
因此,答案是 0。
限制
1 <= words.length <= 50
1 <= words[i].length <= 10
words[i]
仅由小写英文字母组成。
算法
(暴力枚举) $O(n^2m)$
- 暴力枚举所有字符串对,并判断
str1
是否同时为str2
的前后缀。
时间复杂度
- 判断的时间复杂度为 $O(m)$,其中 $m$ 是字符串的长度。
- 故总时间复杂度为 $O(n^2m)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int countPrefixSuffixPairs(vector<string>& words) {
const int n = words.size();
auto isPrefixAndSuffix = [&](const string &str1, const string &str2) {
if (str1.size() > str2.size())
return false;
for (int i = 0; i < str1.size(); i++)
if (str1[i] != str2[i])
return false;
for (int i = str1.size() - 1, j = str2.size() - 1; i >= 0; i--, j--)
if (str1[i] != str2[j])
return false;
return true;
};
int ans = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (isPrefixAndSuffix(words[i], words[j]))
++ans;
return ans;
}
};