##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2023.html

# 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:

## Solution 1. Prefix State Map

• // OJ: https://leetcode.com/problems/number-of-pairs-of-strings-with-concatenation-equal-to-target/
// 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;
}
};

• 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

############

# 2023. Number of Pairs of Strings With Concatenation Equal to Target
# https://leetcode.com/problems/number-of-pairs-of-strings-with-concatenation-equal-to-target/

class Solution:
def numOfPairs(self, nums: List[str], target: str) -> int:
n = len(nums)
t = len(target)
prefix = set()
res = 0

for i in range(1, t):

for i, word1 in enumerate(nums):
if word1 in prefix:
for j, word2 in enumerate(nums):
if i != j and word1 + word2 == target:
res += 1

return res


• class Solution {
public int numOfPairs(String[] nums, String target) {
Map<String, Integer> cnt = new HashMap<>();
for (String x : nums) {
cnt.put(x, cnt.getOrDefault(x, 0) + 1);
}
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;
}
}

• 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
}


## Solution 2. Frequency Map

• // OJ: https://leetcode.com/problems/number-of-pairs-of-strings-with-concatenation-equal-to-target/
// 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;
}
};

• 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

############

# 2023. Number of Pairs of Strings With Concatenation Equal to Target
# https://leetcode.com/problems/number-of-pairs-of-strings-with-concatenation-equal-to-target/

class Solution:
def numOfPairs(self, nums: List[str], target: str) -> int:
n = len(nums)
t = len(target)
prefix = set()
res = 0

for i in range(1, t):

for i, word1 in enumerate(nums):
if word1 in prefix:
for j, word2 in enumerate(nums):
if i != j and word1 + word2 == target:
res += 1

return res


• class Solution {
public int numOfPairs(String[] nums, String target) {
Map<String, Integer> cnt = new HashMap<>();
for (String x : nums) {
cnt.put(x, cnt.getOrDefault(x, 0) + 1);
}
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;
}
}

• 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
}


## Discuss

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