统计前后缀下标对 I

难度: Easy

给你一个下标从 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) 的数量。

示例 1：

输入：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 。

示例 2：

输入：words = ["pa","papa","ma","mama"]
输出：2
解释：在本示例中，计数的下标对包括：
i = 0 且 j = 1 ，因为 isPrefixAndSuffix("pa", "papa") 为 true 。
i = 2 且 j = 3 ，因为 isPrefixAndSuffix("ma", "mama") 为 true 。
因此，答案是 2 。

示例 3：

输入：words = ["abab","ab"]
输出：0
解释：在本示例中，唯一有效的下标对是 i = 0 且 j = 1 ，但是 isPrefixAndSuffix("abab", "ab") 为 false 。
因此，答案是 0 。

提示：

1 <= words.length <= 50
1 <= words[i].length <= 10
words[i] 仅由小写英文字母组成。

Submission

运行时间: 22 ms

内存: 15.9 MB

class Solution:
    def countPrefixSuffixPairs(self, words: List[str]) -> int:
        n = len(words)
        ans = 0
        for i in range(n):
            for j in range(i+1,n):
                if words[j].startswith(words[i]) and words[j].endswith(words[i]):
                    ans += 1
        return ans

Explain

该题解采用了暴力枚举的方法来解决问题。遍历字符串数组中的每一对元素 (words[i], words[j])，其中 i < j，检查是否 words[i] 既是 words[j] 的前缀也是后缀。如果是，则增加计数器。通过双重循环，确保每一个可能的下标对都被检查一次。

时间复杂度: O(n^2 * L)

空间复杂度: O(1)

class Solution:
    def countPrefixSuffixPairs(self, words: List[str]) -> int:
        n = len(words)  # 获取字符串数组的长度
        ans = 0  # 初始化计数器
        for i in range(n):  # 外层循环遍历每个字符串作为前后缀
            for j in range(i+1, n):  # 内层循环遍历所有可能的配对字符串
                if words[j].startswith(words[i]) and words[j].endswith(words[i]):  # 检查是否同时为前缀和后缀
                    ans += 1  # 是的话，计数器加一
        return ans  # 返回满足条件的下标对数量

Explore

暴力枚举方法通常是解决这类问题的最直接和清晰的方法，尤其是在问题的规模较小或者算法的复杂性管理较为困难时。此外，考虑到问题的特殊性——需要检查数组中每一对字符串是否满足特定的前后缀条件，使用暴力枚举可以直接且明确地实现这一目标。尽管暴力枚举可能不是最高效的算法，但它的实现简单，易于理解和调试，适用于初步解决问题或者在数据规模较小的情况下使用。对于更复杂或数据量更大的场景，可以考虑优化或使用更高级的算法技术。

在处理大量数据时，暴力枚举方法的效率通常会显著下降，因为它的时间复杂度通常是O(n^2)，这在数据量大时会导致性能问题。为了优化暴力枚举，可以采用几种策略：1. 减少不必要的比较，例如先通过长度等简单属性快速排除一些不可能的情况。2. 使用更有效的数据结构，如哈希表来存储已经计算过的结果，避免重复计算。3. 在算法设计时预处理数据，例如排序或分类，以减少实际需要检查的配对数量。4. 如果问题允许，还可以使用并行处理或多线程来提高处理速度。

在这个算法中，如果`words[i]`的长度大于`words[j]`，那么`words[i]`不可能同时是`words[j]`的前缀和后缀，因为前缀和后缀的定义要求总长度不超过被比较的字符串。这种情况下，可以在比较之前加入一个长度的判断，如果`words[i]`的长度大于`words[j]`，则直接跳过这一对，避免进行无效的比较。这不仅可以提高算法的效率，还可以避免逻辑上的错误。