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 <= 1001 <= nums[i].length <= 1002 <= target.length <= 100nums[i]andtargetconsist of digits.nums[i]andtargetdo 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): prefix.add(target[:i]) 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): prefix.add(target[:i]) 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