湛江商城网站开发设计,wordpress字体自适应,什么是网络营销师,黑群晖可以做网站吗目录 一、题目
1、题目描述
2、接口描述
3、原题链接
二、解题报告
1、思路分析
2、复杂度
3、代码详解
Python3
c 一、题目
1、题目描述 给你一个下标从 0 开始的字符串数组 words 。 定义一个 布尔 函数 isPrefixAndSuffix #xff0c;它接受两个字符串参数 str…目录 一、题目
1、题目描述
2、接口描述
3、原题链接
二、解题报告
1、思路分析
2、复杂度
3、代码详解
Python3
c 一、题目
1、题目描述 给你一个下标从 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) 的 数量 。 2、接口描述
class Solution {
public:long long countPrefixSuffixPairs(vectorstring words) {}
}; 3、原题链接
3045. 统计前后缀下标对 II 二、解题报告
1、思路分析
之前在周赛题解中用了kmp字典树解法但其实我们可以利用前后缀的特点只用一棵字典树完成求解
对于一个字符串我们可以将其与逆序字符串组合为一个pair列表 s[0], s[n - 1]、s[1], s[n - 2]……s[n - 1], s[0]
然后用字典树存储pair列表这样查询的时候就按照s[0], s[n - 1]、s[1], s[n - 2]……s[n - 1], s[0]往下查询查询了前缀的同时又查询了后缀 python3中我们可以直接用字典映射pairC的话由于小写字母可以映射到0~25所以我们把两个数字的二进制拼接作为映射key即可
2、复杂度 时间复杂度 O(nm)空间复杂度O(nm) 3、代码详解
Python3
class node:__slot__ ch, cntdef __init__(self):self.ch dict()self.cnt 0
class Solution:def countPrefixSuffixPairs(self, words: List[str]) - int:ret 0root node()for s in words:cur rootfor p in zip(s, s[::-1]):if p not in cur.ch:cur.ch[p] node()cur cur.ch[p]ret cur.cntcur.cnt 1return ret
c
struct node{unordered_mapint, node* ch;int cnt 0;
};
class Solution {
public:long long countPrefixSuffixPairs(vectorstring words) {node* root new node;long long ret 0;for(string s : words){node* cur root;for(int i 0, n s.size(); i n; i){int k (int)(s[i] - a) 5 | (int)(s[n - i - 1] - a);if(!cur-ch.count(k)) cur-ch[k] new node;cur cur-ch[k];ret cur-cnt;}cur-cnt;}return ret;}
};
