Skip to content

2023. Number of Pairs of Strings With Concatenation Equal to Target

Description

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.

Solutions

Solution 1: Enumeration

Thinking

With \(n \le 100\) and short strings, enumerate ordered pairs \((i,j)\) and concatenate. \(i \neq j\) means a value can be reused only if it appears twice.

The double loop matches the statement; no preprocess is needed.

Traverse the array nums, for each \(i\), enumerate all \(j\), if \(i \neq j\) and \(nums[i] + nums[j] = target\), then increment the answer by one.

The time complexity is \(O(n^2 \times m)\), where \(n\) and \(m\) are the lengths of the array nums and the string target, respectively. The space complexity is \(O(1)\).

1
2
3
4
5
6
class Solution:
    def numOfPairs(self, nums: List[str], target: str) -> int:
        n = len(nums)
        return sum(
            i != j and nums[i] + nums[j] == target for i in range(n) for j in range(n)
        )

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public int numOfPairs(String[] nums, String target) {
        int n = nums.length;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i != j && target.equals(nums[i] + nums[j])) {
                    ++ans;
                }
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    int numOfPairs(vector<string>& nums, string target) {
        int n = nums.size();
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i != j && nums[i] + nums[j] == target) ++ans;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
func numOfPairs(nums []string, target string) (ans int) {
    for i, a := range nums {
        for j, b := range nums {
            if i != j && a+b == target {
                ans++
            }
        }
    }
    return ans
}

Solution 2: Hash Table

Thinking

Solution 1 concatenates in \(O(m)\) per pair. Every valid pair is some prefix of \(target\) plus the matching suffix.

Count string frequencies, then split \(target\). When prefix equals suffix use \(c(c-1)\) so one index is not paired with itself.

We can use a hash table to count the occurrence of each string in the array nums, then traverse all prefixes and suffixes of the string target. If both the prefix and suffix are in the hash table, then increment the answer by the product of their occurrences.

The time complexity is \(O(n + m^2)\), and the space complexity is \(O(n)\). Here, \(n\) and \(m\) are the lengths of the array nums and the string target, respectively.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def numOfPairs(self, nums: List[str], target: str) -> int:
        cnt = Counter(nums)
        ans = 0
        for i in range(1, len(target)):
            a, b = target[:i], target[i:]
            if a != b:
                ans += cnt[a] * cnt[b]
            else:
                ans += cnt[a] * (cnt[a] - 1)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int numOfPairs(String[] nums, String target) {
        Map<String, Integer> cnt = new HashMap<>();
        for (String x : nums) {
            cnt.merge(x, 1, Integer::sum);
        }
        int ans = 0;
        for (int i = 1; i < target.length(); ++i) {
            String a = target.substring(0, i);
            String b = target.substring(i);
            int x = cnt.getOrDefault(a, 0);
            int y = cnt.getOrDefault(b, 0);
            if (!a.equals(b)) {
                ans += x * y;
            } else {
                ans += x * (y - 1);
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int numOfPairs(vector<string>& nums, string target) {
        unordered_map<string, int> cnt;
        for (auto& x : nums) ++cnt[x];
        int ans = 0;
        for (int i = 1; i < target.size(); ++i) {
            string a = target.substr(0, i);
            string b = target.substr(i);
            int x = cnt[a], y = cnt[b];
            if (a != b) {
                ans += x * y;
            } else {
                ans += x * (y - 1);
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func numOfPairs(nums []string, target string) (ans int) {
    cnt := map[string]int{}
    for _, x := range nums {
        cnt[x]++
    }
    for i := 1; i < len(target); i++ {
        a, b := target[:i], target[i:]
        if a != b {
            ans += cnt[a] * cnt[b]
        } else {
            ans += cnt[a] * (cnt[a] - 1)
        }
    }
    return
}

Comments