2023. Number of Pairs of Strings With Concatenation Equal to Target
Description
Given an array of digit strings nums
and a digit string target
, return the number of pairs of indices (i, j)
(where i != j
) such that the concatenation of nums[i] + nums[j]
equals target
.
Example 1:
Input: nums = ["777","7","77","77"], target = "7777" Output: 4 Explanation: Valid pairs are: - (0, 1): "777" + "7" - (1, 0): "7" + "777" - (2, 3): "77" + "77" - (3, 2): "77" + "77"
Example 2:
Input: nums = ["123","4","12","34"], target = "1234" Output: 2 Explanation: Valid pairs are: - (0, 1): "123" + "4" - (2, 3): "12" + "34"
Example 3:
Input: nums = ["1","1","1"], target = "11" Output: 6 Explanation: Valid pairs are: - (0, 1): "1" + "1" - (1, 0): "1" + "1" - (0, 2): "1" + "1" - (2, 0): "1" + "1" - (1, 2): "1" + "1" - (2, 1): "1" + "1"
Constraints:
2 <= nums.length <= 100
1 <= nums[i].length <= 100
2 <= target.length <= 100
nums[i]
andtarget
consist of digits.nums[i]
andtarget
do not have leading zeros.
Solutions
Solution 1: Enumeration
Traverse the array nums
, for each $i$, enumerate all $j$, if $i \neq j$ and $nums[i] + nums[j] = target$, then increment the answer by one.
The time complexity is $O(n^2 \times m)$, where $n$ and $m$ are the lengths of the array nums
and the string target
, respectively. The space complexity is $O(1)$.
1 2 3 4 5 6 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 |
|
Solution 2: Hash Table
We can use a hash table to count the occurrence of each string in the array nums
, then traverse all prefixes and suffixes of the string target
. If both the prefix and suffix are in the hash table, then increment the answer by the product of their occurrences.
The time complexity is $O(n + m^2)$, and the space complexity is $O(n)$. Here, $n$ and $m$ are the lengths of the array nums
and the string target
, respectively.
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|