Count Prefix and Suffix Pairs I

Leetcode Problem:

• Count Prefix and Suffix Pairs I

Summary

• This solution is designed to count the number of index pairs (i, j) where i < j and isPrefixAndSuffix(words[i], words[j]) is true.

Approach

• The solution uses a nested loop approach to iterate over each pair of words in the input array
• It checks if each word is a prefix and suffix of every other word in the array
• The isPrefixAndSuffix function is used to check this condition
• The time complexity of this approach is O(n^2 * m) where n is the number of words and m is the maximum length of a word.

Complexity

• O(n^2 * m)

Explanation

• The solution starts by initializing a variable ans to 0, which will be used to store the count of index pairs
• It then iterates over each word in the input array using a for loop
• For each word, it iterates over the rest of the words in the array using another for loop
• For each pair of words, it checks if the word is a prefix and suffix of the other word using the isPrefixAndSuffix function
• If it is, it increments the ans variable
• Finally, it returns the ans variable at the end of the function.

Solution Code:

class Solution {
public:
    bool isPrefixAndSuffix(string str1, string str2){
        if(str1.size() > str2.size()) return false;
        for(int i = 0 ; i < str1.size(); i++){
            if(str1[i] != str2[i])return false;
            if(str1[i] != str2[str2.size() - str1.size() + i]) return false;
        }
        return true;
    }
    int countPrefixSuffixPairs(vector& words) {
        int ans = 0;
        for(int i = 0 ; i < words.size(); i++){
            for(int j = i + 1 ; j < words.size(); j++){
                if(isPrefixAndSuffix(words[i], words[j])){
                    ans++;
                }
            }
        }
        return ans;
    }
};