2023

2023. Number of Pairs of Strings With Concatenation Equal to Target (Medium)

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.

Similar Questions:

• Two Sum (Easy)

Solution 1. Prefix State Map

// OJ: https://leetcode.com/problems/number-of-pairs-of-strings-with-concatenation-equal-to-target/
// Author: github.com/lzl124631x
// Time: O(NW) where `N` is the length of `A` and `W` is the maximum length of elements in `A`
// Space: O(U) where `U` is the number of unique strings in `A`.
class Solution {
public:
    int numOfPairs(vector<string>& A, string s) {
        unordered_map<string, int> m;
        int ans = 0;
        for (auto &t : A) {
            if (t.size() > s.size()) continue;
            if (s.substr(0, t.size()) == t) ans += m[s.substr(t.size())];
            m[t]++;
        }
        m.clear();
        reverse(begin(A), end(A));
        for (auto &t : A) {
            if (t.size() > s.size()) continue;
            if (s.substr(0, t.size()) == t) ans += m[s.substr(t.size())];
            m[t]++;
        }
        return ans;
    }
};

Solution 2. Frequency Map

// OJ: https://leetcode.com/problems/number-of-pairs-of-strings-with-concatenation-equal-to-target/
// Author: github.com/lzl124631x
// Time: O(NW) where `N` is the length of `A` and `W` is the maximum length of elements in `A`
// Space: O(U) where `U` is the number of unique strings in `A`.
class Solution {
public:
    int numOfPairs(vector<string>& A, string s) {
        unordered_map<string, int> m;
        for (auto &t : A) m[t]++;
        int ans = 0;
        for (auto &[prefix, cnt] : m) {
            if (prefix.size() > s.size()) continue;
            if (s.substr(0, prefix.size()) == prefix) {
                auto suffix = s.substr(prefix.size());
                ans += m[prefix] * m[suffix];
                if (prefix == suffix) ans -= m[prefix];
            }
        }
        return ans;
    }
};

Discuss

https://leetcode.com/problems/number-of-pairs-of-strings-with-concatenation-equal-to-target/discuss/1499270/C%2B%2B-Frequency-Map