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]
andtarget
consist of digits.nums[i]
andtarget
do not have leading zeros.
Similar Questions:
// 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;
}
};
// 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;
}
};