阿聪的小破站algo›problem
力扣第385场周赛
原题目地址：第385场周赛
100212. 统计前后缀下标对 I
给你一个下标从0开始的字符串数组words
定义一个布尔函数isPrefixAndSuffix，它接受两个字符串参数str1和str2；
- 当str1同时是str2的前缀和后缀时， isPrefixAndSuffix返回true，否则返回false
以整数形式，返回满足i<j 且isPrefixAndSuffix(wrods[i], words[j])为true的下标对(i, j)的数量。
就是按照题目给出的，定义一个方法，来判断str1 是不是str2的前缀和后缀，如果是总是加一。
class Solution:
def countPrefixSuffixPairs(self, words: List[str]) -> int:
count = 0
for i in range(len(words)):
for j in range(i + 1, len(words)):
res = self.isPrefixAndSuffix(words[i], words[j])
if res:
count += 1
return count
def isPrefixAndSuffix(self, s1: str, s2: str) -> bool:
ans = False
if len(s1) > len(s2):
return ans
if len(s1) == len(s2):
pres, backs = s2, s2
else:
pres, backs = s2[:len(s1)], s2[-len(s1):] # pre , bac
if s1 == pres and s1 == backs:
ans = True
return ans100229. 最长公共前缀的长度
这道题我整整磨了1个小时我都没有搞出来， 哎，难受，最大的问题就是代码的时间复杂度太高了，将近O(n^3)，肯定过不了。
这里参考其他大佬的题解理解一下。
就是用集合保存arr1所有的前缀，比如arr1 = [1, 22, 33] , 那么arr1的所有前缀为(1, 2, 22, 3, 33); 然后在遍历arr2，判断当前元素的前缀是否在集合里面，如果不在直接break，在的话，就计算最长公共前缀
class Solution:
def longestCommonPrefix(self, arr1: List[int], arr2: List[int]) -> int:
st = set()
for s in map(str, arr1):
for i in range(1, len(s)+1):
st.add(s[:i])
ans = 0
for s in map(str, arr2):
for i in range(1, len(s) + 1):
if s[:i] not in st:
break
ans = max(ans, len(s[:i]))
return ans100217. 出现频率最高的素数
后面有空再做
100208. 统计前后缀下标对 II
这道题是100212的一个升级版，难度为困难，暂时不做，能力还不够。
补充：需要理解一下力扣的一个分数机制。
第一次双周赛 1500 -> 84.1 ->1415.9， 我做对了一道题， 为什么会扣我84.1分？
第二次周赛：1415.9 +2.9 -> 1418.8 这是啥情况，虽然都是只作对了一道题。
