# Solution For Number Of Pairs Of Strings With Concatenation Equal To Target

Problem Statement:
Given a list of strings words and a string target, find all pairs of indices (i, j) where the concatenation of words[i] + words[j] equals target.

Solution:
To solve this problem, we need to iterate through all the possible pairs of words from the given list and check if their concatenation equals the target string. For this, we can use two nested loops – the outer loop will iterate over all the possible words that can act as the first string (i.e. words[i]), and the inner loop will iterate over the remaining words that can act as the second string (i.e. words[j]). By concatenating words[i] and words[j], we can generate a new string that we can compare with the target to see if they are equal.

Algorithm:
1. Initialize an empty list called res.
2. Iterate over all possible pairs of indices i and j, where i is less than j.
3. Concatenate words[i] and words[j] to create a new string called concat_str.
4. If concat_str is equal to target, append the pair (i,j) to the res list.
5. Return the res list.

Code:

The following code implements the above algorithm in Python:

```python def numOfPairs(words, target): res = [] for i in range(len(words)): for j in range(i+1, len(words)): concat_str = words[i] + words[j] if concat_str == target: res.append((i,j)) concat_str = words[j] + words[i] if concat_str == target: res.append((j,i)) return res```

Time Complexity:
The time complexity of this algorithm is O(n^2), where n is the number of words in the given list. This is because we are iterating over all possible pairs of words to check their concatenation.

Space Complexity:
The space complexity of this algorithm is O(k^2), where k is the maximum length of the strings in the given list. This is because we are storing all possible pairs of indices whose concatenation equals the target in a list called res.

Sample Input and Output:

Input:

words = [“abc”,”def”,”mno”,”xyz”] target = “abcdef”

Output:

[(0, 1), (1, 0)] Explanation:
The concatenation of words[0] and words[1] gives “abcdef”, so we append the pair (0,1) to the res list. Similarly, the concatenation of words[1] and words[0] also gives “abcdef”, so we append the pair (1,0) to the res list.

Input:

words = [“a”,”aa”,”aaa”,”aaaa”] target = “aaaaaa”

Output:

[(0, 3), (1, 2), (3, 0)] Explanation:
The concatenation of words[0] and words[3] gives “aaaaaa”, so we append the pair (0,3) to the res list. Similarly, the concatenation of words[1] and words[2] gives “aaaaaa”, so we append the pair (1,2) to the res list. Also, the concatenation of words[3] and words[0] gives “aaaaaa”, so we append the pair (3,0) to the res list.

## Step by Step Implementation For Number Of Pairs Of Strings With Concatenation Equal To Target

```public int numPairs(String[] words, String target) {

// to store the number of pairs
// of strings with concatenation
// equal to target
int count = 0;

// map to store the frequencies
// of the strings in the array
HashMap map
= new HashMap<>();

// to store the length of each
// string in the array
int[] len = new int[words.length];

// to store the sum of the lengths
// of all the strings in the array
int sum = 0;

// store the length of each string
// and also store the frequencies
// of the strings in the map
for (int i = 0; i < words.length; i++) {
len[i] = words[i].length();
sum += len[i];
map.put(words[i], map.getOrDefault(words[i], 0) + 1);
}

// iterate over all the strings
for (int i = 0; i < words.length; i++) {

// current string
String str = words[i];

// remaining length
int remaining = sum - len[i];

// if the remaining length is equal
// to half of the target length
// then only it is possible to form
// a pair by concatenating the
// current string with some other
// string
if (remaining == target.length() / 2) {

// iterate over all the remaining
// strings
for (int j = i + 1; j < words.length; j++) {

// if the current string is
// equal to the remaining string
// then increment the count
if (str.equals(words[j])) {
count += map.get(str) - 1;
break;
}
}
}
}
return count;
}```
```def numPairs(words, target):

# Initialize an empty list and a counter

pairs = []
count = 0

# Loop through the indices of the list

for i in range(len(words)):

# Loop through the indices of the list starting from the index after the current index

for j in range(i + 1, len(words)):

# If the sum of the two indices is equal to the target,

if (words[i] + words[j]) == target:

# Add the pair to the list

pairs.append((words[i], words[j]))

# Increment the counter

count += 1

# Return the count

return count```
```var numPairs = function(words, target) {
// create a map to store the frequencies of each word
let map = new Map();
// create a variable to store the number of pairs
let pairs = 0;

// loop through the words array
for (let i = 0; i < words.length; i++) {
// if the map already contains the current word
if (map.has(words[i])) {
// increment the frequency of that word
map.set(words[i], map.get(words[i]) + 1);
} else { // the map does not contain the current word
// add the current word to the map with a frequency of 1
map.set(words[i], 1);
}
}

// loop through the words array again
for (let i = 0; i < words.length; i++) {
// calculate the complement of the current word
let complement = target - words[i].length;
// if the map contains the complement and the complement is not the same word as the current word
if (map.has(complement) && complement !== words[i]) {
// increment the number of pairs by the frequency of the complement
pairs += map.get(complement);
}
}

// return the number of pairs
return pairs;
};```
```int numPairs(vector& words, string target) {
unordered_map map;
int res = 0;
for (string word : words) {
map[word]++;
}
for (string word : words) {
int n = target.size();
for (int i = 0; i < n; i++) {
string left = target.substr(0, i);
string right = target.substr(i, n - i);
if (map.count(left) && map.count(right) && left != word && right != word) {
res += map[left] * map[right];
}
}
}
return res / 2;
}```
```public class Solution {
public int NumPairs(string[] words, string target) {
//Create a map to store the count of each word
var map = new Dictionary();
foreach(var word in words)
{
if(!map.ContainsKey(word))
{
}
else
{
map[word]++;
}
}

//Now, for each word, check if the concatenated word is present in the map. If it is, then add the count of that word to the result.
var result = 0;
foreach(var word in words)
{
for(int i = 1; i < target.Length; i++)
{
var left = target.Substring(0, i);
var right = target.Substring(i);

if(map.ContainsKey(left) && map.ContainsKey(right))
{
//If the word is the same as left or right, then we need to make sure that we don't count it twice.
if(word == left)
{
result += map[right];
}
else if(word == right)
{
result += map[left];
}
else
{
result += map[left] * map[right];
}
}
}
}

return result;
}
}```
Scroll to Top

## Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]