连接后等于目标字符串的字符串对 图解题解
这道题到底在问什么
- 输入
- nums=["777","7","77","77"], target="7777"
- 输出
- 4
- 输入
- nums=["123","4","12","34"], target="1234"
- 输出
- 2
- 输入
- nums=["1","1","1"], target="11"
- 输出
- 6
先想最直接的笨办法
四轮枚举全部走完。命中的有序对是 (0, 1)、(1, 0)、(2, 3)、(3, 2):"777"+"7" 和反过来 "7"+"777" 各一对,两个 "77" 正反接成 "77"+"77" 又各一对,合起来正好 4 对,和题面答案对上了。整道题的窍门就一句:枚举所有 i ≠ j 的有序对,拼一次比一次,数出等于 target 的有几对。（动画第 25 步）
最优解：一步一步想明白
- 3记牢这一句:外层固定左串,内层轮流拿右串接上去拼一次、和 target 比一次,i ≠ j 就好。下面每一帧都在套这句。
- 4先看清画面。上面是 nums = ["777","7","77","77"],一共 4 个数字串。我们的目标串 target = "7777"。答案 ans 从 0 起步。接下来紫色的 i 指针会固定一个左串,再让每个右串轮流接上去拼一次、和 target 比一次:拼中了那格标绿,拼不中标红,i 和 j 撞在一起就跳过。先从左串 nums[0] 开始。
- 5第 0 轮开始。紫色 i 指针停在下标 0,把 nums[0] = "777" 定为这一轮的左串。接下来让右串 j 从下标 0 一路走到 3,每停一格就把那格的串接到 "777" 后面,拼出来和 target 对一对。
- 6右串 j 走到下标 0,正好和左串的 i 撞在同一格。题目要求 i ≠ j,同一个位置的字符串不能和它自己拼,所以这一格直接跳过,不拼也不比。j 继续往后走。
- 7右串 j 停在下标 1,把 "7" 接到左串 "777" 后面,拼成 "7777"。它和 target = "7777" 一模一样,命中!这一对 (0, 1) 有效,那格标绿,ans 加到 1。
- 8右串 j 停在下标 2,把 "77" 接到 "777" 后面,拼成 "77777"。它和 target = "7777" 不一样(长度都对不上),不算数,那格标红,ans 不变,还是 1。
- 9右串 j 停在下标 3,把 "77" 接到 "777" 后面,拼成 "77777"。它和 target = "7777" 不一样(长度都对不上),不算数,那格标红,ans 不变,还是 1。
- 10第 1 轮开始。紫色 i 指针停在下标 1,把 nums[1] = "7" 定为这一轮的左串。接下来让右串 j 从下标 0 一路走到 3,每停一格就把那格的串接到 "7" 后面,拼出来和 target 对一对。
- 11右串 j 停在下标 0,把 "777" 接到左串 "7" 后面,拼成 "7777"。它和 target = "7777" 一模一样,命中!这一对 (1, 0) 有效,那格标绿,ans 加到 2。
- 12右串 j 走到下标 1,正好和左串的 i 撞在同一格。题目要求 i ≠ j,同一个位置的字符串不能和它自己拼,所以这一格直接跳过,不拼也不比。j 继续往后走。
- 13右串 j 停在下标 2,把 "77" 接到 "7" 后面,拼成 "777"。它和 target = "7777" 不一样(长度都对不上),不算数,那格标红,ans 不变,还是 2。
- 14右串 j 停在下标 3,把 "77" 接到 "7" 后面,拼成 "777"。它和 target = "7777" 不一样(长度都对不上),不算数,那格标红,ans 不变,还是 2。
- 15第 2 轮开始。紫色 i 指针停在下标 2,把 nums[2] = "77" 定为这一轮的左串。接下来让右串 j 从下标 0 一路走到 3,每停一格就把那格的串接到 "77" 后面,拼出来和 target 对一对。
- 16右串 j 停在下标 0,把 "777" 接到 "77" 后面,拼成 "77777"。它和 target = "7777" 不一样(长度都对不上),不算数,那格标红,ans 不变,还是 2。
- 17右串 j 停在下标 1,把 "7" 接到 "77" 后面,拼成 "777"。它和 target = "7777" 不一样(长度都对不上),不算数,那格标红,ans 不变,还是 2。
- 18右串 j 走到下标 2,正好和左串的 i 撞在同一格。题目要求 i ≠ j,同一个位置的字符串不能和它自己拼,所以这一格直接跳过,不拼也不比。j 继续往后走。
- 19右串 j 停在下标 3,把 "77" 接到左串 "77" 后面,拼成 "7777"。它和 target = "7777" 一模一样,命中!这一对 (2, 3) 有效,那格标绿,ans 加到 3。
- 20第 3 轮开始。紫色 i 指针停在下标 3,把 nums[3] = "77" 定为这一轮的左串。接下来让右串 j 从下标 0 一路走到 3,每停一格就把那格的串接到 "77" 后面,拼出来和 target 对一对。
- 21右串 j 停在下标 0,把 "777" 接到 "77" 后面,拼成 "77777"。它和 target = "7777" 不一样(长度都对不上),不算数,那格标红,ans 不变,还是 3。
- 22右串 j 停在下标 1,把 "7" 接到 "77" 后面,拼成 "777"。它和 target = "7777" 不一样(长度都对不上),不算数,那格标红,ans 不变,还是 3。
- 23右串 j 停在下标 2,把 "77" 接到左串 "77" 后面,拼成 "7777"。它和 target = "7777" 一模一样,命中!这一对 (3, 2) 有效,那格标绿,ans 加到 4。
- 24右串 j 走到下标 3,正好和左串的 i 撞在同一格。题目要求 i ≠ j,同一个位置的字符串不能和它自己拼,所以这一格直接跳过,不拼也不比。j 继续往后走。
- 25四轮枚举全部走完。命中的有序对是 (0, 1)、(1, 0)、(2, 3)、(3, 2):"777"+"7" 和反过来 "7"+"777" 各一对,两个 "77" 正反接成 "77"+"77" 又各一对,合起来正好 4 对,和题面答案对上了。整道题的窍门就一句:枚举所有 i ≠ j 的有序对,拼一次比一次,数出等于 target 的有几对。
⚠️ 容易写错的地方
✗ 错：忘了 i ≠ j,把同一个下标和自己拼也算进去
✓ 对：内层判断里必须带上 i ≠ j 这个条件
题目明确要求两个下标不同。若不排除 i = j,当某个 nums[i] 恰好正反拼自己等于 target 时会多算,更常见的是让计数逻辑跑偏,答案偏大
✗ 错：以为 (i, j) 和 (j, i) 是同一对,只数一次
✓ 对：有序对:两种顺序各拼各比,分别计数
nums[i] + nums[j] 和 nums[j] + nums[i] 拼出来通常不同,题目要的就是有序对。像 "777"+"7" 和 "7"+"777" 都等于 "7777",是两对,漏掉一种答案就少一半
✗ 错：Java 里用等号等号比较拼出来的字符串和 target
✓ 对：用 target.equals(nums[i] + nums[j]) 比内容
Java 的等号等号比的是对象引用是否相同,拼接得到的是新对象,内容一样但引用不同,会被判成不相等。字符串内容比较必须用 equals
✗ 错：拼接前不看长度,任意两串都拼完整个 target 再比
✓ 对：拼出来长度和 target 不一致时可提前判否
只有当 nums[i] 与 nums[j] 长度之和等于 target 长度时才可能相等。长度对不上直接落空,这是一个可选的剪枝,能省下不必要的逐字比较
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
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)
)C++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
int numOfPairs(vector<string>& nums, string target) {
int n = nums.size();
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i != j && nums[i] + nums[j] == target) ++ans;
}
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int numOfPairs(String[] nums, String target) {
int n = nums.length;
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i != j && target.equals(nums[i] + nums[j])) {
++ans;
}
}
}
return ans;
}
}复杂度
时间
O(n² · m)
n 是数组长度,m 是 target 的长度。外层 i、内层 j 各扫 n 次,一共 n 乘 n 个有序对;每对都要做一次字符串拼接和一次比较,拼接与比较的代价随串长走,约为 O(m)。所以总时间是 O(n² · m)。本题 n 和 m 都不超过 100,平方级完全跑得动
空间
O(m)
按峰值算。除计数变量外,每次拼接会临时生成一个长度约为 m 的新字符串来和 target 比,用完即弃,峰值就是这一个临时串的长度 O(m)。不额外开随 n 增长的表,所以空间只和串长有关,不随下标对数量膨胀
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 连接后等于目标字符串的字符串对 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题最直接的思路是什么?+
枚举所有有序下标对 (i, j),只要 i ≠ j,就把 nums[i] 和 nums[j] 拼起来和 target 比一比,相等就计数。因为要的是有序对,内外层都从头扫到尾,(i, j) 与 (j, i) 各判一次。数据范围 n 和 target 长度都不超过 100,这个平方级的暴力枚举完全能过。
有没有更快的做法?+
有。目标串一旦确定,拼接只有一个断点:把 target 从中间某处切成前缀加后缀。所以可以先用哈希表统计每个字符串出现的次数,再枚举 target 的每个切分位置,得到前缀 p 和后缀 s,答案累加 p 的出现次数乘以 s 的出现次数;当 p 和 s 相等时要减掉自己配自己的情况,用出现次数乘以出现次数减一。这样只需枚举 target 的 m 减 1 个切分点;若每次切片都生成新串,时间通常按 O(m²) 估算,哈希表另占 O(n · m) 存储输入串作键,核心计数逻辑比 O(n² · m) 的暴力枚举少扫全部下标对,所以更快。参考代码为了直观用的是暴力枚举,这个哈希切分法可以作为进阶答案。
三种语言实现上要注意什么?+
最容易踩的是 Java 的字符串比较。Java 里等号等号比的是对象引用,拼接得到的是新对象,内容相同但引用不同,会被判不相等,所以必须用 target.equals 比内容。C plus plus 给 string 重载了等号运算符,可以直接用等号等号比内容。Python 更简洁,一行生成器表达式把布尔条件求和就是答案,真算 1 假算 0。三家逻辑一致,差别只在字符串怎么比、循环怎么写。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 连接后等于目标字符串的字符串对 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。