algoadvance

Leetcode 3042. Count Prefix and Suffix Pairs I

Problem Statement

You are given two arrays of strings words1 and words2. A string words1[i] from words1 is a prefix of a string words2[j] from words2 if they both share the same starting characters. Similarly, words1[i] is a suffix of words2[j] if they both share the same ending characters.

Return the number of pairs (i, j) such that words1[i] is a prefix or a suffix of words2[j].

Example:

Input: words1 = ["a", "abc"], words2 = ["abcdef", "abc", "de"]
Output: 4
Explanation: There are 4 pairs: (0, 0), (0, 1), (1, 0), (1, 1)
- "a" is a prefix of "abcdef"
- "a" is a prefix of "abc"
- "abc" is a prefix of "abcdef"
- "abc" is a prefix of "abc"

Clarifying Questions

  1. Clarification on empty arrays: Can words1 or words2 be empty?
  2. Case sensitivity: Are the words case-sensitive?
  3. Character set: Are the words made up of only lowercase English letters?
  4. Length constraints: What are the constraints on the lengths of the words and sizes of the arrays?

Strategy

  1. Initialization: Initialize a counter to zero.
  2. Nesting Loops: Iterate through each word in words1 and for each word, iterate through each word in words2.
  3. Prefix and Suffix Check: For each pair (i, j), check:
    • If words1[i] is a prefix of words2[j]
    • If words1[i] is a suffix of words2[j]
  4. Update Counter: Increment the counter for each valid prefix or suffix found.
  5. Return the Counter: At the end of the iterations, return the counter value.

Code

#include <iostream>
#include <vector>
#include <string>
using namespace std;

// Helper function to check if a is a prefix of b
bool isPrefix(const string &a, const string &b) {
    if (a.size() > b.size()) return false;
    return b.compare(0, a.size(), a) == 0;
}

// Helper function to check if a is a suffix of b
bool isSuffix(const string &a, const string &b) {
    if (a.size() > b.size()) return false;
    return b.compare(b.size() - a.size(), a.size(), a) == 0;
}

int countPrefixSuffixPairs(const vector<string> &words1, const vector<string> &words2) {
    int count = 0;
    for (const string &w1 : words1) {
        for (const string &w2 : words2) {
            if (isPrefix(w1, w2) || isSuffix(w1, w2)) {
                count++;
            }
        }
    }
    return count;
}

int main() {
    vector<string> words1 = {"a", "abc"};
    vector<string> words2 = {"abcdef", "abc", "de"};
    
    int result = countPrefixSuffixPairs(words1, words2);
    cout << "Count of prefix and suffix pairs: " << result << endl;
    return 0;
}

Time Complexity

Let’s denote the length of words1 as m and the length of words2 as n. Also, let L denote the average length of the strings in words1 and words2.

  1. Iterating through pairs: The nested loops result in O(m * n) iterations.
  2. Prefix and Suffix Check: Each check for prefix and suffix takes at most O(L) time.

Thus, the time complexity is O(m * n * L).

This means the function can efficiently handle typical input sizes encountered in practical scenarios while ensuring correctness.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI