What is the main approach for Number of Pairs of Strings With Concatenation Equal to Target?

Use a hash map to store string frequencies and scan the array checking each string as a prefix, then count matching suffixes.

Can we use nested loops for this problem?

Yes, but nested loops yield O(n^2) complexity and can be inefficient; hash-based scanning is faster and safer.

How do duplicates in nums affect counting?

Duplicates require careful handling to avoid counting the same index with itself and to multiply counts correctly using the frequency map.

Does the order of concatenation matter?

Yes, (i, j) and (j, i) are considered different pairs if nums[i] + nums[j] and nums[j] + nums[i] both equal the target.

What is the pattern this problem emphasizes?

It emphasizes the array scanning plus hash lookup pattern for counting valid string concatenations efficiently.

#2023

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

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

给你一个数字字符串数组 nums 和一个数字字符串 target ，请你返回 nums[i] + nums[j] （两个字符串连接）结果等于 target 的下标 (i, j) （需满足 i != j ）的数目。示例 1：输入： nums = ["777","7","77","77"],…

数组哈希表字符串计数

题目描述

给你一个数字字符串数组 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 。

lightbulb

解题思路

方法一：枚举

遍历数组 nums，对于每个 $i$ ，枚举所有 $j$ ，如果 $i \neq j$ 且 $nums[i] + nums[j] = target$ ，则答案加一。

时间复杂度 $O(n^2 \times m)$ ，其中 $n$ 和 $m$ 分别为数组 nums 和字符串 target 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

class Solution:
    def numOfPairs(self, nums: List[str], target: str) -> int:
        n = len(nums)
        return sum(
            i != j and nums[i] + nums[j] == target for i in range(n) for j in range(n)
        )

speed

复杂度分析

指标	值
时间	complexity is O(n * k) where n is the number of strings and k is the average string length, dominated by substring and hash lookups. Space complexity is O(n) for the hash map storing string counts.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Looking for use of hash map to reduce naive O(n^2) pair checks.
question_mark
Interested in handling duplicate strings correctly without overcounting.
question_mark
Expect candidates to separate prefix and suffix logic clearly.

warning

常见陷阱

外企场景

error
Forgetting to exclude self-pairs when prefix equals suffix.
error
Miscounting duplicates by not using frequency map properly.
error
Using nested loops over all pairs which can be slow for larger arrays.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count pairs for a target concatenation with at most one character difference.
arrow_right_alt
Find pairs of strings whose concatenation is a palindrome.
arrow_right_alt
Return the actual list of index pairs instead of just the count.

help

常见问题

外企场景

继续练习

#2053 数组中第 K 个独一无二的字符串 #2085 统计出现过一次的公共字符串 #2131 连接两字母单词得到的最长回文串