今日题目

https://leetcode.com/problems/count-prefix-and-suffix-pairs-i/description/

思路

按题意模拟即可！

方法

两重循环遍历，逐一检查字符串的前缀与后缀。

复杂度

  • 时间复杂度：$O(N^2\times L)$，N 为单词数组的长度，L 为字符串的长度。

  • 空间复杂度：$O(1)$

代码

class Solution:
    def countPrefixSuffixPairs(self, words: List[str]) -> int:
        def checkpre(str1, str2):
            if len(str1) > len(str2):
                return False
            return str1 == str2[:len(str1)]
        
        def checksuf(str1, str2):
            if len(str1) > len(str2):
                return False
            return str1 == str2[len(str2) - len(str1):]
        
        ans = 0
        for i in range(len(words)):
            for j in range(i+1, len(words)):
                if checkpre(words[i],words[j]) and checksuf(words[i], words[j]):
                    ans += 1
        
        return ans

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