统计前后缀下标对 I
难度:
标签:
题目描述
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 <= 501 <= words[i].length <= 10words[i]consists only of lowercase English letters.
代码结果
运行时间: 22 ms, 内存: 15.9 MB
/*
* 思路：
* 1. 创建一个布尔函数isPrefixAndSuffix，判断字符串str1是否是str2的前缀和后缀。
* 2. 使用Java Stream API来遍历所有可能的(i, j)组合，并过滤出isPrefixAndSuffix(words[i], words[j])为true的组合。
* 3. 返回满足条件的组合数量。
*/
import java.util.stream.IntStream;
public class SolutionStream {
public static boolean isPrefixAndSuffix(String str1, String str2) {
return str2.startsWith(str1) && str2.endsWith(str1);
}
public int countPairs(String[] words) {
return (int) IntStream.range(0, words.length)
.boxed()
.flatMap(i -> IntStream.range(i + 1, words.length)
.filter(j -> isPrefixAndSuffix(words[i], words[j]))
.mapToObj(j -> new int[]{i, j}))
.count();
}
public static void main(String[] args) {
SolutionStream solution = new SolutionStream();
String[] words1 = {"a","aba","ababa","aa"};
System.out.println(solution.countPairs(words1)); // 输出: 4
String[] words2 = {"pa","papa","ma","mama"};
System.out.println(solution.countPairs(words2)); // 输出: 2
String[] words3 = {"abab","ab"};
System.out.println(solution.countPairs(words3)); // 输出: 0
}
}解释
方法:
该题解采用了暴力枚举的方法来解决问题。遍历字符串数组中的每一对元素 (words[i], words[j])，其中 i < j，检查是否 words[i] 既是 words[j] 的前缀也是后缀。如果是，则增加计数器。通过双重循环，确保每一个可能的下标对都被检查一次。
时间复杂度:
O(n^2 * L)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么选择暴力枚举方法来解决这个问题，而不是使用更高效的算法？
▷🦆
在暴力枚举中，如何保证算法的执行效率在处理大量数据时不会过度退化？
▷🦆
在比较`words[i]`和`words[j]`时，有没有考虑到当`words[i]`长度大于`words[j]`的情况，这种情况下`words[i]`是否可能同时是`words[j]`的前缀和后缀？
▷