{x}
blog image

Number of Pairs of Strings With Concatenation Equal to Target

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] and target consist of digits.
  • nums[i] and target do not have leading zeros.

Solution Explanation:

The problem asks to find the number of pairs of strings in the input array nums whose concatenation equals the target string. Two approaches are presented: brute force enumeration and a hash table-based solution.

Approach 1: Brute Force Enumeration

This approach directly implements the problem definition. It iterates through all possible pairs of strings in nums. For each pair, it concatenates the strings and checks if the result is equal to the target string. If it matches and the indices are different, the counter is incremented.

Time Complexity: O(n²m), where n is the length of nums and m is the length of the target string. This is because we have nested loops iterating through all pairs (n²) and string concatenation/comparison takes O(m) time in the worst case.

Space Complexity: O(1). The algorithm uses a constant amount of extra space.

Approach 2: Hash Table (Optimized)

This approach leverages a hash table (or dictionary in Python) to significantly improve efficiency. It first counts the occurrences of each string in nums. Then, it iterates through all possible splits of the target string. For each split, it checks if both the prefix and suffix strings exist in the hash table. If they do, it calculates their contribution to the total count, accounting for cases where the prefix and suffix are the same string.

Time Complexity: O(n + m²), where n is the length of nums and m is the length of the target string. Building the hash table takes O(n) time. Iterating through the splits of the target string takes O(m) iterations, and each iteration involves a constant time lookup in the hash table. The overall complexity is dominated by O(m²) due to the splits.

Space Complexity: O(n), because the hash table stores the counts of each unique string in nums.

Code Implementation in Multiple Languages:

The code implementations below demonstrate both approaches. The hash table approach is generally preferred for its better time complexity, especially when dealing with larger input arrays and longer target strings.

Python:

from collections import Counter
 
class Solution:
    def numOfPairs(self, nums: List[str], target: str) -> int:
        # Approach 2: Hash Table
        cnt = Counter(nums)
        ans = 0
        for i in range(1, len(target)):
            prefix = target[:i]
            suffix = target[i:]
            if prefix != suffix:
                ans += cnt[prefix] * cnt[suffix]
            else:
                ans += cnt[prefix] * (cnt[prefix] - 1)  # Account for same prefix/suffix
        return ans
 
    # Approach 1: Brute Force (For comparison)
    def numOfPairs_bruteforce(self, nums: List[str], target: str) -> int:
        count = 0
        n = len(nums)
        for i in range(n):
            for j in range(n):
                if i != j and nums[i] + nums[j] == target:
                    count += 1
        return count

Java:

import java.util.HashMap;
import java.util.Map;
 
class Solution {
    public int numOfPairs(String[] nums, String target) {
        // Approach 2: Hash Table
        Map<String, Integer> countMap = new HashMap<>();
        for (String num : nums) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }
        int ans = 0;
        for (int i = 1; i < target.length(); i++) {
            String prefix = target.substring(0, i);
            String suffix = target.substring(i);
            if (!prefix.equals(suffix)) {
                ans += countMap.getOrDefault(prefix, 0) * countMap.getOrDefault(suffix, 0);
            } else {
                int count = countMap.getOrDefault(prefix, 0);
                ans += count * (count - 1);
            }
        }
        return ans;
 
        //Approach 1: Brute Force (For comparison)
        // int count = 0;
        // for (int i = 0; i < nums.length; i++) {
        //     for (int j = 0; j < nums.length; j++) {
        //         if (i != j && (nums[i] + nums[j]).equals(target)) {
        //             count++;
        //         }
        //     }
        // }
        // return count;
    }
}

C++:

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
 
using namespace std;
 
class Solution {
public:
    int numOfPairs(vector<string>& nums, string target) {
        // Approach 2: Hash Table
        unordered_map<string, int> countMap;
        for (const string& num : nums) {
            countMap[num]++;
        }
        int ans = 0;
        for (int i = 1; i < target.length(); ++i) {
            string prefix = target.substr(0, i);
            string suffix = target.substr(i);
            if (prefix != suffix) {
                ans += countMap[prefix] * countMap[suffix];
            } else {
                ans += countMap[prefix] * (countMap[prefix] - 1);
            }
        }
        return ans;
 
        // Approach 1: Brute Force (For comparison)
        // int count = 0;
        // for (int i = 0; i < nums.size(); ++i) {
        //     for (int j = 0; j < nums.size(); ++j) {
        //         if (i != j && nums[i] + nums[j] == target) {
        //             count++;
        //         }
        //     }
        // }
        // return count;
    }
};

Go:

package main
 
import (
	"fmt"
	"strings"
)
 
func numOfPairs(nums []string, target string) int {
	// Approach 2: Hash Table
	countMap := make(map[string]int)
	for _, num := range nums {
		countMap[num]++
	}
	ans := 0
	for i := 1; i < len(target); i++ {
		prefix := target[:i]
		suffix := target[i:]
		if prefix != suffix {
			ans += countMap[prefix] * countMap[suffix]
		} else {
			ans += countMap[prefix] * (countMap[prefix] - 1)
		}
	}
	return ans
 
    // Approach 1: Brute Force (For Comparison)
    // count := 0
    // for i := 0; i < len(nums); i++ {
    //     for j := 0; j < len(nums); j++ {
    //         if i != j && nums[i]+nums[j] == target {
    //             count++
    //         }
    //     }
    // }
    // return count
}
 
func main() {
    nums := []string{"777", "7", "77", "77"}
    target := "7777"
    fmt.Println(numOfPairs(nums, target)) // Output: 4
}

Remember to choose the appropriate approach based on the constraints of your problem; for most cases, the hash table solution will be far more efficient.