Leetcode 3042: Count Prefix and Suffix Pairs I
You are given a 0-indexed string array
words. You need to determine the number of index pairs (i, j) such that i < j and the string at index i is both a prefix and a suffix of the string at index j. The function isPrefixAndSuffix(str1, str2) returns true if str1 is both a prefix and a suffix of str2, and false otherwise.Problem
Approach
Steps
Complexity
Input: You are given an array `words` of strings.
Example: words = ["ab", "abab", "abc", "ababc"]
Constraints:
• 1 <= words.length <= 50
• 1 <= words[i].length <= 10
• words[i] consists only of lowercase English letters.
Output: Return an integer representing the number of valid index pairs `(i, j)` where `i < j` and `isPrefixAndSuffix(words[i], words[j])` is true.
Example: For the input words = ["ab", "abab", "abc", "ababc"], the output is 1.
Constraints:
• Return 0 if no such pairs exist.
Goal: The function should iterate through all pairs `(i, j)` with `i < j` and check whether the word at index `i` is both a prefix and a suffix of the word at index `j`. If this condition is met, the pair is valid, and the counter should be incremented.
Steps:
• Iterate through all pairs of indices (i, j) with i < j.
• For each pair, check if the word at index i is a prefix and suffix of the word at index j.
• If both conditions are true, increment the counter.
• Finally, return the count.
Goal: The array contains lowercase English words, and each word has a length of at most 10 characters. The total number of words does not exceed 50.
Steps:
• 1 <= words.length <= 50
• 1 <= words[i].length <= 10
Assumptions:
• The input contains only lowercase English letters.
• Each word can be a valid prefix and suffix for another word in the array.
• Input: words = ["ab", "abab", "abc", "ababc"]
• Explanation: In this case, the only valid pair is i = 0 and j = 1, because 'ab' is a prefix and suffix of 'abab'. The result is 1.
Approach: The approach is to iterate through all pairs of indices (i, j) with i < j and check if the string at index i is both a prefix and suffix of the string at index j.
Observations:
• Prefix and suffix matching should be checked efficiently.
• We can check if a string is a prefix of another string using substring matching, and similarly for suffix matching.
Steps:
• Iterate through all pairs of words in the array.
• For each pair (i, j), check if words[i] is both a prefix and a suffix of words[j].
• Use a helper function to check if a word is both a prefix and suffix of another word.
• Count how many valid pairs satisfy the condition.
Empty Inputs:
• If words array is empty, return 0.
Large Inputs:
• For large inputs, ensure the algorithm performs efficiently.
Special Values:
• If no valid pairs exist, return 0.
Constraints:
• Handle cases with words of varying lengths efficiently.
vector<string> wds;
bool pre(int i, int j) {
int p = 0, q = 0;
if(wds[j].size() < wds[i].size()) return false;
while(p < wds[i].size() && q < wds[j].size() && wds[i][p] == wds[j][q]) {
p++; q++;
}
return p == wds[i].size();
}
bool post(int i, int j) {
int p = wds[i].size() - 1, q = wds[j].size() - 1;
if(p > q) return false;
while(p >= 0 && q >= 0 && wds[i][p] == wds[j][q]) {
p--; q--;
}
return p == -1;
}
int countPrefixSuffixPairs(vector<string>& w) {
wds = w;
int n = w.size(), cnt = 0;
for(int i = 0; i < n; i++)
for(int j = i + 1; j < n; j++)
if(pre(i, j) && post(i, j)) cnt++;
return cnt;
}
1 : Variable Initialization
vector<string> wds;
Declares a global vector `wds` to store the input list of strings for processing in the `pre` and `post` functions.
2 : Function Definition
bool pre(int i, int j) {
Defines the helper function `pre` that checks if the string at index `i` is a prefix of the string at index `j`.
3 : Variable Initialization
int p = 0, q = 0;
Initializes two variables `p` and `q` to iterate over the characters of the strings at indices `i` and `j` respectively.
4 : Size Check
if(wds[j].size() < wds[i].size()) return false;
Checks if the string at index `j` is smaller than the string at index `i`. If true, returns `false` since the smaller string cannot be a prefix.
5 : Prefix Check Loop
while(p < wds[i].size() && q < wds[j].size() && wds[i][p] == wds[j][q]) {
Begins a loop that compares each character of both strings until either a mismatch is found or the end of one string is reached.
6 : Character Comparison
p++; q++;
Increments the indices `p` and `q` to move to the next characters in both strings.
7 : Prefix Check Return
return p == wds[i].size();
Returns `true` if the entire string at index `i` matches the beginning of the string at index `j` (i.e., string `i` is a prefix of string `j`).
8 : Function Definition
bool post(int i, int j) {
Defines the helper function `post` that checks if the string at index `i` is a suffix of the string at index `j`.
9 : Variable Initialization
int p = wds[i].size() - 1, q = wds[j].size() - 1;
Initializes `p` and `q` to point to the last characters of the strings at indices `i` and `j`, respectively.
10 : Size Check
if(p > q) return false;
Checks if the string at index `i` is larger than the string at index `j`. If true, returns `false` since the larger string cannot be a suffix.
11 : Suffix Check Loop
while(p >= 0 && q >= 0 && wds[i][p] == wds[j][q]) {
Begins a loop that compares each character of both strings from the end until either a mismatch is found or the beginning of one string is reached.
12 : Character Comparison
p--; q--;
Decrements the indices `p` and `q` to move to the previous characters in both strings.
13 : Suffix Check Return
return p == -1;
Returns `true` if the entire string at index `i` matches the end of the string at index `j` (i.e., string `i` is a suffix of string `j`).
14 : Function Definition
int countPrefixSuffixPairs(vector<string>& w) {
Defines the function `countPrefixSuffixPairs` that counts how many pairs of strings in the input vector `w` satisfy the prefix-suffix conditions.
15 : Copy Input List
wds = w;
Copies the input vector `w` to the global `wds` for further processing.
16 : Variable Initialization
int n = w.size(), cnt = 0;
Initializes `n` to the size of the input vector `w` and `cnt` to count the valid prefix-suffix pairs.
17 : Nested Loops
for(int i = 0; i < n; i++)
Begins the outer loop to iterate over each string `i` in the input vector `w`.
18 : Inner Loop
for(int j = i + 1; j < n; j++)
Begins the inner loop to iterate over each string `j` that comes after string `i` in the input vector `w`.
19 : Check Prefix-Suffix Pair
if(pre(i, j) && post(i, j)) cnt++;
Checks if the strings `i` and `j` form a valid prefix-suffix pair. If true, increments the count `cnt`.
20 : Return Result
return cnt;
Returns the final count of valid prefix-suffix pairs.
Best Case: O(n^2 * m), where n is the number of words and m is the maximum length of a word.
Average Case: O(n^2 * m).
Worst Case: O(n^2 * m), where n is the number of words and m is the maximum length of a word.
Description: We check all pairs of words and compare their prefixes and suffixes.
Best Case: O(1), as no extra space is required.
Worst Case: O(n), where n is the number of words, for storing the array.
Description: Space complexity is mainly determined by the space needed to store the input array.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus