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

难度: Medium

给你一个数字字符串数组 nums 和一个数字字符串 target ，请你返回 nums[i] + nums[j] （两个字符串连接）结果等于 target 的下标 (i, j) （需满足 i != j）的数目。

示例 1：

输入：nums = ["777","7","77","77"], target = "7777"
输出：4
解释：符合要求的下标对包括：
- (0, 1)："777" + "7"
- (1, 0)："7" + "777"
- (2, 3)："77" + "77"
- (3, 2)："77" + "77"

示例 2：

输入：nums = ["123","4","12","34"], target = "1234"
输出：2
解释：符合要求的下标对包括
- (0, 1)："123" + "4"
- (2, 3)："12" + "34"

示例 3：

输入：nums = ["1","1","1"], target = "11"
输出：6
解释：符合要求的下标对包括
- (0, 1)："1" + "1"
- (1, 0)："1" + "1"
- (0, 2)："1" + "1"
- (2, 0)："1" + "1"
- (1, 2)："1" + "1"
- (2, 1)："1" + "1"

提示：

2 <= nums.length <= 100
1 <= nums[i].length <= 100
2 <= target.length <= 100
nums[i] 和 target 只包含数字。
nums[i] 和 target 不含有任何前导 0 。

Submission

运行时间: 28 ms

内存: 16.1 MB

class Solution:
    def numOfPairs(self, nums: List[str], target: str) -> int:
        counter, res = Counter(nums), 0
        for num,cnt in counter.items():
            l = len(num)
            if target[:l] == num and target[l:] in counter:
                res += cnt*(cnt-1 if target[l:]==num else counter[target[l:]])
        return res
        # return sum(1 for i in range(len(nums)) for j in range(len(nums)) if i!=j and nums[i]+nums[j]==target)

Explain

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

时间复杂度: O(n + m*k)

空间复杂度: O(n)

class Solution:
    def numOfPairs(self, nums: List[str], target: str) -> int:
        counter, res = Counter(nums), 0  # 创建字符串计数器和结果累加器
        for num, cnt in counter.items():  # 遍历每个字符串及其出现次数
            l = len(num)  # 当前字符串的长度
            if target[:l] == num and target[l:] in counter:  # 如果当前字符串是target的前缀且剩余部分在counter中
                res += cnt * (cnt - 1 if target[l:] == num else counter[target[l:]])  # 计算符合条件的对数
        return res  # 返回结果
        # return sum(1 for i in range(len(nums)) for j in range(len(nums)) if i!=j and nums[i]+nums[j]==target)

Explore

在算法实现中，保证`i`和`j`不相等的机制是通过条件检查实现的。在双层遍历的情况下（不使用哈希表优化的解法），我们会使用两个嵌套循环，并在内循环中加入条件`if i != j`来确保`i`和`j`不相同。在哈希表的优化方法中，这一点通过检查两个不同字符串或同一字符串的不同使用情况来实现。例如，如果前缀与剩余部分相同（即`target[l:] == num`），我们使用`cnt * (cnt - 1)`，这里`cnt - 1`代表除去当前使用的一个实例后其他可用的数量，从而确保不会重复使用相同的下标。

这是因为当`target[l:]`等于`num`时，我们在考虑将同一个字符串`num`使用两次来形成`target`。但是，因为`i`和`j`必须是不同的，我们不能重复使用同一个元素的索引。因此，若`num`的数量为`cnt`，第一个`num`使用了一个实例后，剩下的可用`num`数量为`cnt - 1`。所以，符合条件的对数是每个`num`可以与它后面剩余的`cnt - 1`个`num`组合，总共是`cnt * (cnt - 1)`种情况。

如果`nums`数组中存在空字符串，它可以作为任何字符串的前缀或后缀。因此，在算法中，空字符串`""`与任何字符串`x`连接时都等于`x`。如果`target`字符串本身就是一个空字符串，则任意两个空字符串连接都会符合条件。如果`target`不是空字符串，空字符串可以作为前缀或后缀参与到组合中，其计算方式与正常字符串相同。具体的影响取决于`target`是否包含空字符串作为其组成部分以及空字符串在`nums`中的数量。