统计前后缀下标对 II
难度:
标签:
题目描述
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)returnstrueifstr1is both a prefix and a suffix ofstr2, andfalseotherwise.
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 that i < j, and isPrefixAndSuffix(words[i], words[j]) is true.
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 <= 1051 <= words[i].length <= 105words[i]consists only of lowercase English letters.- The sum of the lengths of all
words[i]does not exceed5 * 105.
代码结果
运行时间: 159 ms, 内存: 32.3 MB
/*
题目思路：
使用Java Stream来解决这个问题。我们可以通过双重流循环来遍历所有可能的(i, j)对，并使用filter方法来筛选出符合条件的对，最终计算它们的数量。
*/
import java.util.stream.IntStream;
public class Solution {
public boolean isPrefixAndSuffix(String str1, String str2) {
int len1 = str1.length();
int len2 = str2.length();
if (len1 > len2) return false;
return str2.startsWith(str1) && str2.endsWith(str1);
}
public long countPrefixAndSuffixPairs(String[] words) {
return IntStream.range(0, words.length)
.boxed()
.flatMap(i -> IntStream.range(i + 1, words.length)
.filter(j -> isPrefixAndSuffix(words[i], words[j]))
.boxed())
.count();
}
public static void main(String[] args) {
Solution solution = new Solution();
String[] words = {"a","aba","ababa","aa"};
System.out.println(solution.countPrefixAndSuffixPairs(words)); // 输出：4
}
}解释
方法:
此题解采用了逆序遍历与哈希表的结合来优化查询和统计过程。首先，从数组的尾部开始遍历，使用哈希表s2c来记录遍历过的每个字符串及其出现次数。对于每个字符串words[i]，检查它是否为已记录在哈希表中的每个字符串的前缀和后缀。如果是，则累加对应字符串的计数到结果中。此方法避免了重复的字符串比较，利用哈希表快速地检索和更新字符串的出现次数。
时间复杂度:
O(n^2 * l)
空间复杂度:
O(n * l)
代码细节讲解
🦆
为什么选择从数组的尾部向前遍历而不是从头部开始遍历？这种遍历方向对算法的效率有何影响？
▷🦆
哈希表s2c在算法中扮演了什么角色，它是如何帮助减少计算量的？
▷🦆
在更新哈希表s2c时，为什么选择使用 get 方法，并且如何确保它的正确性和高效性？
▷