leetcode contest 385

难得 AK 的题目，最近比较好的成绩，也可能全部都是字符串匹配的问题。

100212. 统计前后缀下标对 I

给你一个下标从 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] 仅由小写英文字母组成。

地址

https://leetcode.cn/contest/weekly-contest-385/problems/count-prefix-and-suffix-pairs-i/

题意

直接模拟即可

思路

直接模拟即可，利用 python的切片可以直接实现。
复杂度分析：

时间复杂度：$O(n)$，其中 $n$ 表示给定数组的长度。
空间复杂度：$O(1)$。

代码

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

100229. 最长公共前缀的长度

给你两个 正整数 数组 arr1 和 arr2 。

正整数的前缀是其 最左边 的一位或多位数字组成的整数。例如，123 是整数 12345 的前缀，而 234 不是。

设若整数 c 是整数 a 和 b 的 公共前缀 ，那么 c 需要同时是 a 和 b 的前缀。例如，5655359 和 56554 有公共前缀 565 ，而 1223 和 43456 没有公共前缀。

你需要找出属于 arr1 的整数 x 和属于 arr2 的整数 y 组成的所有数对 (x, y) 之中最长的公共前缀的长度。

返回所有数对之中最长公共前缀的长度。如果它们之间不存在公共前缀，则返回 0 。

示例 1：

输入：arr1 = [1,10,100], arr2 = [1000]
输出：3
解释：存在 3 个数对 (arr1[i], arr2[j]) ：
- (1, 1000) 的最长公共前缀是 1 。
- (10, 1000) 的最长公共前缀是 10 。
- (100, 1000) 的最长公共前缀是 100 。
最长的公共前缀是 100 ，长度为 3 。

示例 2：

输入：arr1 = [1,2,3], arr2 = [4,4,4]
输出：0
解释：任何数对 (arr1[i], arr2[j]) 之中都不存在公共前缀，因此返回 0 。
请注意，同一个数组内元素之间的公共前缀不在考虑范围内。

提示：

1 <= arr1.length, arr2.length <= 5 * 104
1 <= arr1[i], arr2[i] <= 108

地址

https://leetcode.cn/contest/weekly-contest-385/problems/find-the-length-of-the-longest-common-prefix/

题意

字典树，哈希表

思路

字典树的解法就比较简单了，每次添加新的字符串时搜索所有的字典树中的最长公共前缀即可。还可以用哈希算法，由于每个字符串的长度为 $m$，因此最多有 $mn$ 个不同的前缀，我们直接构造 $mn$ 个前缀即可。然后检测是否存在最长的前缀即可。
复杂度分析：

时间复杂度：$O(n \log U)$, $n$ 表示给定字符串 $s$ 的长度；
空间复杂度：$O(n)$；

代码

class TrieNode:
    def __init__(self):
        self.next = [None] * 10
        self.isEnd = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, s):
        node = self.root
        for c in s:
            x = ord(c) - ord('0')
            if node.next[x] is None:
                node.next[x] = TrieNode()
            node = node.next[x]
        node.isEnd = True
    
    def search(self, s):
        res = 0
        node = self.root
        for c in s:
            x = ord(c) - ord('0')
            if node.next[x] is None:
                return res
            node = node.next[x]
            res += 1
        return res
        
class Solution:
    def longestCommonPrefix(self, arr1: List[int], arr2: List[int]) -> int:
        res = 0
        trie = Trie()
        for s in arr1:
            trie.insert(str(s))
        for s in arr2:
            res = max(res, trie.search(str(s)))
        return res
             
                
class Solution:
    def longestCommonPrefix(self, arr1: List[int], arr2: List[int]) -> int:
        st = set()
        for v in arr1:
            while v > 0:
                st.add(v)
                v = v // 10
        res = 0
        for v in arr2:
            while v > 0:
                if v in st:
                    res = max(res, v)
                v  = v // 10
        return 0 if res == 0 else len(str(res))

100217. 出现频率最高的素数

给你一个大小为 m x n 、下标从 0 开始的二维矩阵 mat 。在每个单元格，你可以按以下方式生成数字：

最多有 8 条路径可以选择：东，东南，南，西南，西，西北，北，东北。
选择其中一条路径，沿着这个方向移动，并且将路径上的数字添加到正在形成的数字后面。
注意，每一步都会生成数字，例如，如果路径上的数字是 1, 9, 1，那么在这个方向上会生成三个数字：1, 19, 191 。

返回在遍历矩阵所创建的所有数字中，出现频率最高的、大于 10的素数；如果不存在这样的素数，则返回 -1 。如果存在多个出现频率最高的素数，那么返回其中最大的那个。

注意：移动过程中不允许改变方向。

示例 1：

输入：mat = [[1,1],[9,9],[1,1]]
输出：19
解释： 
从单元格 (0,0) 出发，有 3 个可能的方向，这些方向上可以生成的大于 10 的数字有：
东方向: [11], 东南方向: [19], 南方向: [19,191] 。
从单元格 (0,1) 出发，所有可能方向上生成的大于 10 的数字有：[19,191,19,11] 。
从单元格 (1,0) 出发，所有可能方向上生成的大于 10 的数字有：[99,91,91,91,91] 。
从单元格 (1,1) 出发，所有可能方向上生成的大于 10 的数字有：[91,91,99,91,91] 。
从单元格 (2,0) 出发，所有可能方向上生成的大于 10 的数字有：[11,19,191,19] 。
从单元格 (2,1) 出发，所有可能方向上生成的大于 10 的数字有：[11,19,19,191] 。
在所有生成的数字中，出现频率最高的素数是 19 。

示例 2：

输入：mat = [[7]]
输出：-1
解释：唯一可以生成的数字是 7 。它是一个素数，但不大于 10 ，所以返回 -1 。

示例 3：

输入：mat = [[9,7,8],[4,6,5],[2,8,6]]
输出：97
解释： 
从单元格 (0,0) 出发，所有可能方向上生成的大于 10 的数字有: [97,978,96,966,94,942] 。
从单元格 (0,1) 出发，所有可能方向上生成的大于 10 的数字有: [78,75,76,768,74,79] 。
从单元格 (0,2) 出发，所有可能方向上生成的大于 10 的数字有: [85,856,86,862,87,879] 。
从单元格 (1,0) 出发，所有可能方向上生成的大于 10 的数字有: [46,465,48,42,49,47] 。
从单元格 (1,1) 出发，所有可能方向上生成的大于 10 的数字有: [65,66,68,62,64,69,67,68] 。
从单元格 (1,2) 出发，所有可能方向上生成的大于 10 的数字有: [56,58,56,564,57,58] 。
从单元格 (2,0) 出发，所有可能方向上生成的大于 10 的数字有: [28,286,24,249,26,268] 。
从单元格 (2,1) 出发，所有可能方向上生成的大于 10 的数字有: [86,82,84,86,867,85] 。
从单元格 (2,2) 出发，所有可能方向上生成的大于 10 的数字有: [68,682,66,669,65,658] 。
在所有生成的数字中，出现频率最高的素数是 97 。

提示：

m == mat.length
n == mat[i].length
1 <= m, n <= 6
1 <= mat[i][j] <= 9

地址

https://leetcode.cn/contest/weekly-contest-385/problems/most-frequent-prime/

题意

模拟

思路

该题目暴力模拟 $8$ 个方向，直到出现相关符合题目要求的素数即可，直接暴力模拟即可
复杂度分析：

时间复杂度：$O(nm\times(m+m) + mn\times sqrt(U))$，其中 $m,n$ 分别表示矩阵中的行数与列数。
空间复杂度：$O(|\Sigma|)$， $|\Sigma|$ 表示字符集的大小。

代码

def check(x):
    for i in range(2, isqrt(x) + 1):
        if x % i == 0:
            return False
    return True

class Solution:
    def mostFrequentPrime(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        cnt = {}
        dir = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
        for i in range(m):
            for j in range(n):
                for k in range(8):
                    x = mat[i][j]
                    nx = i + dir[k][0]
                    ny = j + dir[k][1]
                    while 0 <= nx < m and 0 <= ny < n:
                        x = x * 10 + mat[nx][ny]
                        cnt[x] = cnt.get(x, 0) + 1
                        nx += dir[k][0]
                        ny += dir[k][1]
                        
        res, freq = -1, 0
        for k, v in cnt.items():
            if check(k) and (v > freq or (v == freq and k > res)):
                res, freq = k, v
        return res

100208. 统计前后缀下标对 II

给你一个下标从 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 <= 105
1 <= words[i].length <= 105
words[i] 仅由小写英文字母组成。
所有 words[i] 的长度之和不超过 5 * 105 。

地址

https://leetcode.cn/contest/weekly-contest-385/problems/count-prefix-and-suffix-pairs-ii/

题意

字符串哈希

思路

题目最难的在于如何判断出现相同的后缀与前缀，当然我们可以利用 kmp或者难懂的 Z函数，但是最简单的方法还是字符串哈希算法，本题目使用哈希的话就非常常规的题目，对于每个字符串，我们统计其前缀与后缀相等的长度，并计算其哈希值，然后统计字符串中是否存在相同的哈希值的字符串的数目即可。
复杂度分析：

时间复杂度：$O(mn)$，其中 $m,n$ 分别表示数组的长度与字符串的平均长度。
空间复杂度：$O(m)$， $m$ 表示数组的长度。

代码

class Solution:
    def countPrefixSuffixPairs(self, words: List[str]) -> int:
        mx = max(len(w) for w in words)
        base, mod = 31, 10**9 + 7
        h = [1] * (mx + 1)
        for i in range(1, mx + 1):
            h[i] = h[i - 1] * base % mod
        cnt = {}
        res = 0
        for w in words:
            pre, suf = 0, 0
            for j in range(len(w)):
                pre = (pre * base + ord(w[j]) - ord('a') + 1) % mod
                suf = (h[j] * (ord(w[len(w) - j - 1]) - ord('a') + 1) % mod + suf) % mod
                if pre == suf:
                    res += cnt.get(pre, 0)
            cnt[pre] = cnt.get(pre, 0) + 1
        return res

欢迎关注和打赏，感谢支持！

关注我的博客: https://mike-box.github.io/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu

Tags: 题解力扣周赛赛

← leetcode contest 382 leetcode biweekly contest 124 →

扫描二维码，分享此文章