2023. 連接后等于目標字符串的字符串對
給你一個 數字?字符串數組 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 。
解題思路
- 使用map記錄每個字符串出現的下標，因為可能存在相同的字符串出現在不同下標，因此下標使用vector進行維護
- 遍歷所有字符串，假設其組成的是target的前部分，使用map快速判斷是否存在其他下標的字符串可以組成target的后部分
例如對于第一個樣例：
nums = ["777","7","77","77"], target = "7777"
- 對于nums[0]=“777”，map中存在“7”可以與其構成“7777”,并且下標與其不相等
- 對于nums[1]=“7”，map中存在“777”可以與其構成“7777”,并且下標與其不相等
- 對于nums[2]=“77”，map中存在“77”可以與其構成“77”,只存在一個下標與其不相等，所以答案只能加一
- 對于nums[3]=“777”，map中存在“77”可以與其構成“77”,只存在一個下標與其不相等，所以答案只能加一
代碼
class Solution {
public:int numOfPairs(vector<string>& nums, string target) {map<string,vector<int>> m;for (int i = 0; i < nums.size(); ++i) {m[nums[i]].push_back(i);}int res(0);for (int i = 0; i < nums.size(); ++i) {if (target.size()<nums[i].size())continue;string front= target.substr(0,nums[i].size());string back=target.substr(nums[i].size(),target.size()-nums[i].size());if (nums[i]==front&&m.count(back)){for(auto t:m[back])if (t!=i)res++;}}return res;}
};
)
