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

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

给你一个数字字符串数组 nums 和一个数字字符串 target 。请你统计并返回 nums 中满足下述条件的不同有序数对 (i, j) 的数目：

0 <= i, j < nums.length
i != j
nums[i] 与 nums[j] 拼接而成的字符串等于 target

说明： 「拼接」指将两个字符串首尾相接，例如 "ab" 与 "cd" 拼接为 "abcd"。

# 示例 1

项目	内容
输入	`nums = ["777","7","77","77"]`, `target = "7777"`
输出	`4`
解释	合法的有序数对为 `(0, 1)`、`(1, 0)`、`(2, 3)`、`(3, 2)`。

# 示例 2

项目	内容
输入	`nums = ["123","4","12","34"]`, `target = "1234"`
输出	`2`
解释	合法的有序数对为 `(0, 1)`、`(2, 3)`。

# 示例 3

项目	内容
输入	`nums = ["1","1","1"]`, `target = "11"`
输出	`6`
解释	任意两个不同下标均可，共 `6` 组有序数对。

# 提示

2 <= nums.length <= 100
1 <= nums[i].length <= 100
2 <= target.length <= 100
nums[i] 和 target 仅由数字组成
nums[i] 和 target 不含前导零

# 思路

将 target 在任意合法位置切成两段非空前缀与后缀，记为 A 和 B，则一对下标 (p, q) 合法当且仅当 nums[p] 等于 A 且 nums[q] 等于 B。先用哈希表统计 nums 中每个字符串出现的次数。

对每一种切分，设 A 的出现次数为 ca，B 的出现次数为 cb。若 A 与 B 不相等，则第一个串取 A、第二个串取 B 的有序对数量为 ca 乘以 cb。若 A 与 B 相等，则需两个下标不同，从 ca 个下标里选第一个再选第二个，数量为 ca 乘以 ca - 1。

枚举 target 上从第 1 个字符后到倒数第 1 个字符前的所有切断位置，将各切分对应的贡献相加即为答案。切分种数不超过 target 的长度，配合哈希查询，复杂度与 nums 长度及 target 长度有关，在题目数据范围内可行。

# 解法

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int numOfPairs(String[] nums, String target) {
        Map<String, Integer> cnt = new HashMap<>();
        for (String s : nums) {
            cnt.merge(s, 1, Integer::sum);
        }
        long ans = 0;
        int n = target.length();
        for (int k = 1; k < n; k++) {
            String a = target.substring(0, k);
            String b = target.substring(k);
            int ca = cnt.getOrDefault(a, 0);
            int cb = cnt.getOrDefault(b, 0);
            if (ca == 0 || cb == 0) {
                continue;
            }
            if (a.equals(b)) {
                ans += (long) ca * (cb - 1);
            } else {
                ans += (long) ca * cb;
            }
        }
        return (int) ans;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

# 总结

将 target 在任意合法位置切成两段非空前缀与后缀，记为 A 和 B，则一对下标 (p, q) 合法当且仅当 nums[p] 等于 A 且 nums[q] 等于 B。
先用哈希表统计 nums 中每个字符串出现的次数。
对每一种切分，设 A 的出现次数为 ca，B 的出现次数为 cb。
若 A 与 B 不相等，则第一个串取 A、第二个串取 B 的有序对数量为 ca 乘以 cb。
若 A 与 B 相等，则需两个下标不同，从 ca 个下标里选第一个再选第二个，数量为 ca 乘以 ca - 1。

#Java