Number Of Pairs Of Strings With Concatenation Equal To Target - Leetcode Solution

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:

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.

1