leetcode
leetcode 1751 ~ 1800
连接后等于目标字符串的字符串对

连接后等于目标字符串的字符串对

难度:

标签:

题目描述

代码结果

运行时间: 28 ms, 内存: 16.1 MB


/*
题目思路:
1. 使用 Java Stream 处理,结合外层的传统 for 循环。
2. 外层循环遍历 nums,内层使用 Stream 过滤和计数满足条件的元素。
*/

import java.util.Arrays;

public class Solution {
    public int numOfPairs(String[] nums, String target) {
        return (int) Arrays.stream(nums)
            .flatMap(num1 -> Arrays.stream(nums)
            .filter(num2 -> !num1.equals(num2) && (num1 + num2).equals(target)))
            .count();
    }
}

解释

方法:

该题解采用了哈希表来优化查找过程。首先,利用Counter对nums中的元素进行计数,记录每个字符串出现的次数。遍历哈希表中的每个元素,对于每个字符串,检查它是否为目标字符串target的前缀。如果是,计算剩余部分(即target去掉该前缀后的部分),检查该剩余部分是否存在于哈希表中。如果存在,根据前缀和剩余部分是否相同,有不同的计算方式:如果相同,说明是用同一字符串两次形成target,此时应该用该字符串的出现次数乘以次数减一(因为不能重用相同的索引);如果不同,直接乘以剩余部分字符串的出现次数。这样可以有效地计算出所有符合条件的字符串对的数量。

时间复杂度:

O(n + m*k)

空间复杂度:

O(n)

代码细节讲解

🦆
在算法中,如何确保`nums[i] + nums[j]`的结果中`i`和`j`不相等?
在算法实现中,保证`i`和`j`不相等的机制是通过条件检查实现的。在双层遍历的情况下(不使用哈希表优化的解法),我们会使用两个嵌套循环,并在内循环中加入条件`if i != j`来确保`i`和`j`不相同。在哈希表的优化方法中,这一点通过检查两个不同字符串或同一字符串的不同使用情况来实现。例如,如果前缀与剩余部分相同(即`target[l:] == num`),我们使用`cnt * (cnt - 1)`,这里`cnt - 1`代表除去当前使用的一个实例后其他可用的数量,从而确保不会重复使用相同的下标。
🦆
哈希表方法中,如果`target[l:]`等于`num`,为何使用`cnt * (cnt - 1)`而不是`cnt * cnt`来计算符合条件的对数?
这是因为当`target[l:]`等于`num`时,我们在考虑将同一个字符串`num`使用两次来形成`target`。但是,因为`i`和`j`必须是不同的,我们不能重复使用同一个元素的索引。因此,若`num`的数量为`cnt`,第一个`num`使用了一个实例后,剩下的可用`num`数量为`cnt - 1`。所以,符合条件的对数是每个`num`可以与它后面剩余的`cnt - 1`个`num`组合,总共是`cnt * (cnt - 1)`种情况。
🦆
如何处理`nums`数组中存在空字符串的情况?会对结果产生什么影响?
如果`nums`数组中存在空字符串,它可以作为任何字符串的前缀或后缀。因此,在算法中,空字符串`""`与任何字符串`x`连接时都等于`x`。如果`target`字符串本身就是一个空字符串,则任意两个空字符串连接都会符合条件。如果`target`不是空字符串,空字符串可以作为前缀或后缀参与到组合中,其计算方式与正常字符串相同。具体的影响取决于`target`是否包含空字符串作为其组成部分以及空字符串在`nums`中的数量。

相关问题