Question

2023. 连接后等于目标字符串的字符串对

English Version

题目描述

给你一个 数字 字符串数组 nums 和一个 数字 字符串 target ，请你返回 nums[i] + nums[j] （两个字符串连接）结果等于 target 的下标 (i, j) （需满足 i != j）的数目。

 

示例 1：

输入：nums = ["777","7","77","77"], target = "7777"
输出：4
解释：符合要求的下标对包括：
- (0, 1)："777" + "7"
- (1, 0)："7" + "777"
- (2, 3)："77" + "77"
- (3, 2)："77" + "77"

示例 2：

输入：nums = ["123","4","12","34"], target = "1234"
输出：2
解释：符合要求的下标对包括
- (0, 1)："123" + "4"
- (2, 3)："12" + "34"

示例 3：

输入：nums = ["1","1","1"], target = "11"
输出：6
解释：符合要求的下标对包括
- (0, 1)："1" + "1"
- (1, 0)："1" + "1"
- (0, 2)："1" + "1"
- (2, 0)："1" + "1"
- (1, 2)："1" + "1"
- (2, 1)："1" + "1"

 

提示：

• 2 <= nums.length <= 100
• 1 <= nums[i].length <= 100
• 2 <= target.length <= 100
• nums[i] 和 target 只包含数字。
• nums[i] 和 target 不含有任何前导 0 。

解法

方法一：枚举

遍历数组 nums，对于每个 $i$，枚举所有 $j$，如果 $i \neq j$ 且 $nums[i] + nums[j] = target$，则答案加一。

时间复杂度 $O(n^2 \times m)$，其中 $n$ 和 $m$ 分别为数组 nums 和字符串 target 的长度。空间复杂度 $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
}

方法二：哈希表

我们可以用哈希表统计数组 nums 中每个字符串出现的次数，然后遍历字符串 target 的所有前缀和后缀，如果前缀和后缀都在哈希表中，则答案加上它们出现的次数的乘积。

时间复杂度 $O(n + m^2)$，空间复杂度 $O(n)$。其中 $n$ 和 $m$ 分别为数组 nums 和字符串 target 的长度。

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
}