Problem

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.

Examples

Example 1:

1
2
3
4
5
6
7

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:

1
2
3
4
5

Input: nums = ["123","4","12","34"], target = "1234"
Output: 2
Explanation: Valid pairs are:
- (0, 1): "123" + "4"
- (2, 3): "12" + "34"

Example 3:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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"

Solution

Method 1 - Nested loop with concatenation check

  1. Initial Thoughts:
    • We will check all possible pairs of indices (i, j) where i != j.
    • For each pair, concatenate nums[i] and nums[j].
    • Check if this concatenated result equals target.
  2. Steps:
    • Iterate through each element in nums as the first part of the pair (i).
    • For each i, iterate through each element in nums as the second part of the pair (j) where i != j.
    • Count the number of times the concatenated result matches target.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int numOfPairs(String[] nums, String target) {
        int ans = 0;

        // Looping through all pairs of indices i, j
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length; j++) {
                if (i != j) {
                    // Concatenating nums[i] and nums[j] and checking if it equals target
                    if ((nums[i] + nums[j]).equals(target)) {
                        ans++;
                    }
                }
            }
        }

        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def numOfPairs(self, nums: List[str], target: str) -> int:
        ans: int = 0

        # Looping through all pairs of indices i, j
        for i in range(len(nums)):
            for j in range(len(nums)):
                if i != j:
                    # Concatenating nums[i] and nums[j] and checking if it equals target
                    if nums[i] + nums[j] == target:
                        ans += 1

        return ans

Complexity

  • Time: O(n^2), where n is the length of the nums array. There are two nested loops, each running n times.
  • Space: O(1), - since we are using a constant amount of extra space for the answer variable.