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

All Problems

All Solutions