Leetcode 2023: Number of Pairs of Strings With Concatenation Equal to Target
You are given an array of digit strings
nums and a target digit string target. Count the number of valid pairs of indices (i, j) where i != j such that the concatenation of nums[i] and nums[j] equals target.Problem
Approach
Steps
Complexity
Input: The input consists of an array `nums` of digit strings and a target digit string `target`.
Example: nums = ["123", "4", "12", "34"], target = "1234"
Constraints:
• 2 <= nums.length <= 100
• 1 <= nums[i].length <= 100
• 2 <= target.length <= 100
• nums[i] and target consist of digits.
Output: Return the number of valid pairs of indices `(i, j)` where `i != j` such that `nums[i] + nums[j] == target`.
Example: Output: 2
Constraints:
• The valid pairs must not have the same index for both `i` and `j`.
Goal: The goal is to find all pairs of strings `nums[i]` and `nums[j]` such that their concatenation equals the target.
Steps:
• 1. Create a frequency map to count occurrences of strings in `nums` that are smaller than `target` in length.
• 2. Loop through the frequency map and check if the prefix of `target` matches each string in `nums`.
• 3. If a valid prefix is found, find the corresponding suffix in the `nums` array and update the count of valid pairs.
Goal: The constraints on the input values.
Steps:
• 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.
Assumptions:
• All strings in `nums` and the `target` contain only digits and are non-empty.
• The solution should efficiently handle arrays with up to 100 elements.
• Input: nums = ["123", "4", "12", "34"], target = "1234"
• Explanation: The valid pairs are (0, 1) for "123" + "4" and (2, 3) for "12" + "34".
• Input: nums = ["1", "1", "1"], target = "11"
• Explanation: There are 6 valid pairs: (0, 1), (1, 0), (0, 2), (2, 0), (1, 2), (2, 1).
Approach: We can solve this problem by checking each pair of strings in `nums` and checking if their concatenation equals `target`.
Observations:
• Using a frequency map allows us to efficiently check pairs.
• By checking for valid prefixes and suffixes, we avoid the need for checking every possible pair of strings.
Steps:
• 1. Create a frequency map to count how many times each string appears in `nums`.
• 2. For each string in `nums`, check if it is a valid prefix of the target string and find the matching suffix.
• 3. Count the number of valid pairs.
Empty Inputs:
• If `nums` is empty, return 0.
Large Inputs:
• Make sure the solution handles arrays of size 100 efficiently.
Special Values:
• If the `target` contains very large values or repetitive patterns, the solution should still work efficiently.
Constraints:
• Avoid out-of-bounds errors and make sure the solution handles all possible cases.
int numOfPairs(vector<string>& nums, string target) {
unordered_map<string, int> freq;
for(auto num : nums) if(num.size() < target.size()) freq[num]++;
int res = 0;
for(auto [s, frq]: freq) {
if(target.find(s) == 0) {
if(s + s == target)
res += frq * (frq - 1);
else
res += frq * freq[target.substr(s.size())];
}
}
return res;
}
1 : Function Definition
int numOfPairs(vector<string>& nums, string target) {
This defines the function 'numOfPairs', which takes a vector of strings 'nums' and a target string 'target'. It will return the number of valid pairs of strings that concatenate to form the target string.
2 : Variable Initialization
unordered_map<string, int> freq;
This initializes an unordered map 'freq' to store the frequency of strings in 'nums' that are shorter than the target string.
3 : Loop Over Input
for(auto num : nums) if(num.size() < target.size()) freq[num]++;
This loop iterates through each string in 'nums'. If the string's size is smaller than the target string, it increases its frequency in the 'freq' map.
4 : Variable Initialization
int res = 0;
This initializes an integer 'res' to store the final result, which will be the count of valid pairs.
5 : Iterating Through Frequencies
for(auto [s, frq]: freq) {
This loop iterates over each entry in the 'freq' map, where 's' is the string and 'frq' is its frequency.
6 : Prefix Check
if(target.find(s) == 0) {
This checks if the string 's' is a prefix of the target string (i.e., 's' starts at the beginning of the target string).
7 : Self-Pair Check
if(s + s == target)
This checks if the string 's' repeated twice matches the target string.
8 : Count Self-Pairs
res += frq * (frq - 1);
This adds the number of valid self-pairs to the result. If 's + s == target', the number of pairs is calculated using the formula 'frq * (frq - 1)', where 'frq' is the frequency of 's'.
9 : Else Case
else
This else statement handles the case where 's' is a prefix but not equal to the target string when repeated.
10 : Count Valid Pairs
res += frq * freq[target.substr(s.size())];
This adds to the result the number of valid pairs where the remaining part of the target string (after removing 's') can be found in the 'freq' map.
11 : Return Statement
return res;
This returns the result 'res', which is the total count of valid pairs of strings that concatenate to form the target string.
Best Case: O(n)
Average Case: O(n * m)
Worst Case: O(n * m)
Description: We iterate through the array of strings and use a frequency map to find matching pairs, where `n` is the number of strings and `m` is the average length of strings.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is proportional to the size of the frequency map, which stores strings from the `nums` array.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus