Leetcode

Number of Pairs of Strings With Concatenation Equal to Target

May 26, 2022 by aAshish

  • Time:O(|\texttt{nums}|)
  • Space:O(|\texttt{nums}|)

C++

 
class Solution {
 public:
  int numOfPairs(vector<string>& nums, string target) {
    const int n = target.length();
    int ans = 0;
    unordered_map<string, int> count;

    for (const string& num : nums) {
      const int k = num.length();
      if (k >= n)
        continue;
      if (target.substr(0, k) == num)
        ans += count[target.substr(k)];
      if (target.substr(n - k) == num)
        ans += count[target.substr(0, n - k)];
      ++count[num];
    }

    return ans;
  }
};

JAVA

 
class Solution {
  public int numOfPairs(String[] nums, String target) {
    final int n = target.length();
    int ans = 0;
    Map<String, Integer> count = new HashMap<>();

    for (final String num : nums) {
      final int k = num.length();
      if (k >= n)
        continue;
      if (target.substring(0, k).equals(num))
        ans += count.getOrDefault(target.substring(k), 0);
      if (target.substring(n - k).equals(num))
        ans += count.getOrDefault(target.substring(0, n - k), 0);
      count.merge(num, 1, Integer::sum);
    }

    return ans;
  }
}

Python

 
class Solution:
  def numOfPairs(self, nums: List[str], target: str) -> int:
    ans = 0
    count = Counter()

    for num in nums:
      k = len(num)
      if target[:k] == num:
        ans += count[target[k:]]
      if target[-k:] == num:
        ans += count[target[:-k]]
      count[num] += 1

    return ans