3042. 统计前后缀下标对 I

🟢   🔖  字典树 数组 字符串 字符串匹配 哈希函数 滚动哈希  🔗 力扣 LeetCode

题目

You are given a 0-indexed string array words.

Let's define a boolean function isPrefixAndSuffix that takes two strings, str1 and str2:

• isPrefixAndSuffix(str1, str2) returns true if str1 is both a prefix and a suffix of str2, and false otherwise.

For example, isPrefixAndSuffix("aba", "ababa") is true because "aba" is a prefix of "ababa" and also a suffix, but isPrefixAndSuffix("abc", "abcd") is false.

Return an integer denoting the number of index pairs (i, j)such thati < j , andisPrefixAndSuffix(words[i], words[j])istrue .

Example 1:

Input: words = ["a","aba","ababa","aa"]

Output: 4

Explanation: In this example, the counted index pairs are:

i = 0 and j = 1 because isPrefixAndSuffix("a", "aba") is true.

i = 0 and j = 2 because isPrefixAndSuffix("a", "ababa") is true.

i = 0 and j = 3 because isPrefixAndSuffix("a", "aa") is true.

i = 1 and j = 2 because isPrefixAndSuffix("aba", "ababa") is true.

Therefore, the answer is 4.

Example 2:

Input: words = ["pa","papa","ma","mama"]

Output: 2

Explanation: In this example, the counted index pairs are:

i = 0 and j = 1 because isPrefixAndSuffix("pa", "papa") is true.

i = 2 and j = 3 because isPrefixAndSuffix("ma", "mama") is true.

Therefore, the answer is 2.

Example 3:

Input: words = ["abab","ab"]

Output: 0

Explanation: In this example, the only valid index pair is i = 0 and j = 1, and isPrefixAndSuffix("abab", "ab") is false.

Therefore, the answer is 0.

Constraints:

• 1 <= words.length <= 50
• 1 <= words[i].length <= 10
• words[i] consists only of lowercase English letters.

题目大意

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

解题思路

思路一：双层循环暴力法

• 外层循环遍历每个字符串 words[i]。
• 内层循环从 i + 1 开始遍历剩余字符串 words[j]。
• 检查：
  • 如果 words[i] 长度大于 words[j]，则跳过，优化效率。
  • 否则判断 words[i] 是否是 words[j] 的前缀且后缀。
  • 使用 JavaScript 的字符串方法 startsWith 和 endsWith 分别检查前缀和后缀关系。
• 如果满足条件，计数器 count 增加。

复杂度分析

• 时间复杂度：O(n^2 * m)
  • 外层循环遍历 n 个字符串，内层循环最多遍历 n-1 个字符串，在最坏情况下需要比较所有的字符串对，因此时间复杂度为 O(n^2)。
  • 每次比较字符串的前缀和后缀时，复杂度与字符串的长度 m 成正比，因此整体复杂度为 O(n^2 * m)，其中 m 是字符串的平均长度。
• 空间复杂度：O(1)，仅使用了常数级别的辅助变量。

---

思路二：前缀树法

为了提高效率，可以使用前缀树（Trie）和后缀树分别处理前缀和后缀匹配，从而优化暴力解法的时间复杂度。

1. 构建前缀树和后缀树：

   • 前缀树（Prefix Trie）： 用于快速判断某个字符串是否是另一个字符串的前缀。
   • 后缀树（Suffix Trie）： 用于快速判断某个字符串是否是另一个字符串的后缀。
   • 遍历所有字符串，将每个字符串插入到前缀树和后缀树中。
   • 插入到后缀树时，先将字符串反转，这样后缀匹配变成前缀匹配。

2. 查询前缀和后缀匹配：

   • 对于当前字符串前面的每个字符串，查询它是否同时是当前字符串的前缀和后缀。

3. 计数：

   • 如果满足条件，增加计数。

复杂度分析

• 时间复杂度：O(n * m)
  • 构建前缀树和后缀树的时间复杂度是 O(n * m)，其中 n 是字符串数量，m 是字符串的平均长度。
  • 每个字符串查询前缀和后缀的时间复杂度是 O(m)，总复杂度是 O(n * m)。
• 空间复杂度：O(n * m)，前缀树和后缀树的存储复杂度为 O(n * m)，需要存储所有字符串的节点。

代码

双层循环暴力法

/**
 * @param {string[]} words
 * @return {number}
 */
var countPrefixSuffixPairs = function (words) {
	let count = 0;

	// 遍历每个字符串对
	for (let i = 0; i < words.length; i++) {
		for (let j = i + 1; j < words.length; j++) {
			// 如果 words[i] 比 words[j] 长，直接跳过
			if (words[i].length > words[j].length) {
				continue;
			}

			// 检查 words[i] 是否为 words[j] 的前缀和后缀
			if (words[j].startsWith(words[i]) && words[j].endsWith(words[i])) {
				count++;
			}
		}
	}

	return count;
};

前缀树法

/**
 * @param {string[]} words
 * @return {number}
 */
var countPrefixSuffixPairs = function (words) {
	let count = 0;
	const n = words.length;
	for (let i = 0; i < n; i++) {
		// 构建前缀树和后缀树
		const prefixTrie = new Trie();
		const suffixTrie = new Trie();
		// 插入前缀树
		prefixTrie.insert(words[i]);
		// 插入后缀树（反转字符串）
		suffixTrie.insert([...words[i]].reverse().join(''));

		// 遍历每个字符串，查询前缀和后缀匹配
		for (let j = 0; j < i; j++) {
			// 如果 words[j] 比 words[i] 长，直接跳过
			if (words[i].length < words[j].length) continue;

			const word = words[j];
			const reversedWord = [...word].reverse().join('');
			if (prefixTrie.startsWith(word) && suffixTrie.startsWith(reversedWord)) {
				count++;
			}
		}
	}
	return count;
};
class TrieNode {
	constructor() {
		this.children = {}; // 子节点映射
		this.isEnd = false; // 标记是否是某个字符串的结束
	}
}
class Trie {
	constructor() {
		this.root = new TrieNode();
	}
	// 插入字符串
	insert(str) {
		let node = this.root;
		for (let char of str) {
			if (!node.children[char]) {
				node.children[char] = new TrieNode();
			}
			node = node.children[char];
		}
		node.isEnd = true;
	}
	// 查询是否为前缀
	startsWith(prefix) {
		let node = this.root;
		for (let char of prefix) {
			if (!node.children[char]) {
				return false;
			}
			node = node.children[char];
		}
		return true;
	}
}

相关题目

题号	标题	题解	标签	难度	力扣
208	实现 Trie (前缀树)	[✓]	设计 字典树 哈希表 1+	🟠	🀄️ 🔗
211	添加与搜索单词 - 数据结构设计	[✓]	深度优先搜索 设计 字典树 1+	🟠	🀄️ 🔗