Easy

题目描述

给你一个下标从 0 开始的字符串数组 words。

定义一个布尔函数 isPrefixAndSuffix，它接受两个字符串参数 str1 和 str2：

  • 当 str1 同时是 str2 的前缀和后缀时，isPrefixAndSuffix(str1, str2) 返回 true，否则返回 false。

例如，isPrefixAndSuffix("aba", "ababa") 返回 true，因为 “aba” 既是 “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] 仅由小写英文字母组成

解题思路

这是一个简单的字符串匹配问题。我们需要遍历所有可能的下标对 (i, j)，其中 i < j，然后检查 words[i] 是否同时是 words[j] 的前缀和后缀。

主要思路：

  1. 暴力枚举：遍历所有满足 i < j 的下标对。
  2. 前缀后缀检查：对于每对字符串，检查 words[i] 是否既是 words[j] 的前缀又是后缀。
  3. 优化判断条件：首先检查长度关系，如果 words[i] 的长度大于 words[j]，直接跳过。

具体实现：

  • 使用内置的字符串方法检查前缀和后缀
  • 前缀检查：words[j].startswith(words[i]) 或 words[j].substr(0, len) == words[i]
  • 后缀检查：words[j].endswith(words[i]) 或比较字符串尾部

时间复杂度分析： 由于数组长度最多 50，字符串长度最多 10，暴力解法完全可行。对于每个字符串对，检查前缀和后缀的时间复杂度为 O(m)，其中 m 是较短字符串的长度。

推荐解法： 直接使用暴力枚举配合字符串内置方法，代码简洁且效率足够。

代码实现

class Solution {
public:
    int countPrefixSuffixPairs(vector<string>& words) {
        int count = 0;
        int n = words.size();
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isPrefixAndSuffix(words[i], words[j])) {
                    count++;
                }
            }
        }
        
        return count;
    }
    
private:
    bool isPrefixAndSuffix(const string& str1, const string& str2) {
        int len1 = str1.length();
        int len2 = str2.length();
        
        if (len1 > len2) return false;
        
        // Check prefix
        if (str2.substr(0, len1) != str1) return false;
        
        // Check suffix
        if (str2.substr(len2 - len1) != str1) return false;
        
        return true;
    }
};

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

public class Solution {
    public int CountPrefixSuffixPairs(string[] words) {
        int count = 0;
        int n = words.Length;
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (IsPrefixAndSuffix(words[i], words[j])) {
                    count++;
                }
            }
        }
        
        return count;
    }
    
    private bool IsPrefixAndSuffix(string str1, string str2) {
        if (str1.Length > str2.Length) return false;
        
        return str2.StartsWith(str1) && str2.EndsWith(str1);
    }
}

var countPrefixSuffixPairs = function(words) {
    let count = 0;
    const n = words.length;
    
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (isPrefixAndSuffix(words[i], words[j])) {
                count++;
            }
        }
    }
    
    return count;
};

function isPrefixAndSuffix(str1, str2) {
    if (str1.length > str2.length) return false;
    
    return str2.startsWith(str1) && str2.endsWith(str1);
}
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n² × m)
空间复杂度O(1)

其中 n 是字符串数组的长度，m 是字符串的平均长度。在最坏情况下，需要检查所有字符串对，每次检查需要 O(m) 时间来比较前缀和后缀。

相关题目