[Programming Problem] Number of Pairs of Strings With Concatenation Equal to Target

[Problem Link]

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"

My initial thought was to use some sort of advanced pattern searching algorithm like Robin Karp. But there was a more straightforward way simply using hashtables (involing suffixes and prefixes).

– Add all suffixes and prefixes of target into a set
– Loop through nums and check if both suffix and prefix are part of the set.
– Gotcha: In the example, target=’7777′ nums: [‘7777’, ‘777’], (0, 1) would show up as a pair which its clearly not.
– Add another condition to make sure length of nums[i] + nums[j] equals length of target.
– Another gotcha was how we build suffixes (look at comment below).

/**
 * @param {string[]} nums
 * @param {string} target
 * @return {number}
 */
var numOfPairs = function(nums, target) {
    const prefixes = new Set();
    const suffixes = new Set();
 
    let curr = '';
    for ( let i = 0 ; i < target.length ; i++ ) {
        curr += target[i];
        prefixes.add(curr);
    }
 
    curr = '';
    for ( let i = target.length-1 ; i >= 0 ; i-- ) {
        // curr += target[i] will fail.
        // If you do that, you'll be comparing suffixes in reverse order.
        curr = target[i] + curr; 
        suffixes.add(curr);
    }
 
    let cnt = 0;
    for ( let i = 0 ; i < nums.length ; i++ ) {
        for ( let j = 0 ; j < nums.length ; j++ ) {
            if ( i === j ) continue;
            if ( 
                prefixes.has(nums[i]) &&
                suffixes.has(nums[j]) &&
                (nums[i].length + nums[j].length) === target.length  ) {
                    cnt++
                }            
        }
    }
 
    return cnt;
};

[Programming Problem] Number of Pairs of Strings With Concatenation Equal to Target

softwareeveryday