Question

2023. Number of Pairs of Strings With Concatenation Equal to Target

中文文档

Description

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.

Solutions

Solution 1: Enumeration

Traverse the array nums, for each $i$, enumerate all $j$, if $i \neq j$ and $nums[i] + nums[j] = target$, then increment the answer by one.

The time complexity is $O(n^2 \times m)$, where $n$ and $m$ are the lengths of the array nums and the string target, respectively. The space complexity is $O(1)$.

class Solution:
  def numOfPairs(self, nums: List[str], target: str) -> int:
    n = len(nums)
    return sum(
      i != j and nums[i] + nums[j] == target for i in range(n) for j in range(n)
    )

class Solution {
  public int numOfPairs(String[] nums, String target) {
    int n = nums.length;
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        if (i != j && target.equals(nums[i] + nums[j])) {
          ++ans;
        }
      }
    }
    return ans;
  }
}

class Solution {
public:
  int numOfPairs(vector<string>& nums, string target) {
    int n = nums.size();
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        if (i != j && nums[i] + nums[j] == target) ++ans;
      }
    }
    return ans;
  }
};

func numOfPairs(nums []string, target string) (ans int) {
  for i, a := range nums {
    for j, b := range nums {
      if i != j && a+b == target {
        ans++
      }
    }
  }
  return ans
}

Solution 2: Hash Table

We can use a hash table to count the occurrence of each string in the array nums, then traverse all prefixes and suffixes of the string target. If both the prefix and suffix are in the hash table, then increment the answer by the product of their occurrences.

The time complexity is $O(n + m^2)$, and the space complexity is $O(n)$. Here, $n$ and $m$ are the lengths of the array nums and the string target, respectively.

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

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

class Solution {
public:
  int numOfPairs(vector<string>& nums, string target) {
    unordered_map<string, int> cnt;
    for (auto& x : nums) ++cnt[x];
    int ans = 0;
    for (int i = 1; i < target.size(); ++i) {
      string a = target.substr(0, i);
      string b = target.substr(i);
      int x = cnt[a], y = cnt[b];
      if (a != 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
}