Count Prefix and Suffix Pairs I

Problem Statement

In this challenge, you are provided with an array of strings, words, indexed from 0. You need to define and utilize a boolean function, isPrefixAndSuffix, which takes two strings, str1 and str2. The function returns true when str1 acts as both the starting prefix and the ending suffix of str2, but returns false if either condition does not hold.

For instance, in the provided examples, the string "aba" is both a prefix and a suffix of "ababa", hence for this pair, the function would return true. Conversely, "abc" does not fulfil these conditions for "abcd" and would therefore return false.

Your task is to count and return the number of unique index pairs (i, j) from the words array for which i < j and isPrefixAndSuffix(words[i], words[j]) returns true.

Examples

Example 1

Input:

words = ["a","aba","ababa","aa"]

Output:

4

Explanation:

In this example, the counted index pairs are:
i = 0 and j = 1 because isPrefixAndSuffix("a", "aba") is true.
i = 0 and j = 2 because isPrefixAndSuffix("a", "ababa") is true.
i = 0 and j = 3 because isPrefixAndSuffix("a", "aa") is true.
i = 1 and j = 2 because isPrefixAndSuffix("aba", "ababa") is true.
Therefore, the answer is 4.

Example 2

Input:

words = ["pa","papa","ma","mama"]

Output:

2

Explanation:

In this example, the counted index pairs are:
i = 0 and j = 1 because isPrefixAndSuffix("pa", "papa") is true.
i = 2 and j = 3 because isPrefixAndSuffix("ma", "mama") is true.
Therefore, the answer is 2.

Example 3

Input:

words = ["abab","ab"]

Output:

0

Explanation:

In this example, the only valid index pair is i = 0 and j = 1, and isPrefixAndSuffix("abab", "ab") is false.
Therefore, the answer is 0.

Constraints

• 1 <= words.length <= 50
• 1 <= words[i].length <= 10
• words[i] consists only of lowercase English letters.

Approach and Intuition

To address the problem, the first step involves understanding how to implement the isPrefixAndSuffix function:

1. Verify if str1 is the prefix of str2.
2. Simultaneously, check if str1 is the suffix of str2.

Simply put, for str1 to be a prefix, str2 should start with str1. Likewise, for str1 to be a suffix, str2 should end with str1. Both these conditions must simultaneously hold for the function to return true.

The core of the solution involves a nested loop approach:

1. Loop through each index i of the words array.
2. For each i, loop through the subsequent indices j (i < j constraint).
3. Call the isPrefixAndSuffix function with words[i] and words[j]:
   • If the function returns true, increment a counter.
4. Finally, the counter that tracks the number of valid pairs is returned.

With specific constraints ensuring words length is no more than 50 and individual strings are at most 10 characters long, this nested loop approach is computationally feasible. Though not the most optimal in terms of efficiency for larger datasets, it effectively leverages the manageable input size constraints to provide a solution that is both intuitive and straightforward to implement.

Solutions

class TrieNode {
public:
    TrieNode* children[26] = {};
    
    bool hasKey(char ch) { return children[ch - 'a'] != nullptr; }
    
    void setChild(char ch, TrieNode* node) { children[ch - 'a'] = node; }
    
    TrieNode* getChild(char ch) { return children[ch - 'a']; }
};
    
class TrieStructure {
public:
    TrieNode* rootHead;
    
    TrieStructure() { rootHead = new TrieNode(); }
    
    void addWord(string& word) {
        TrieNode* tempNode = rootHead;
        for (char ch : word) {
            if (!tempNode->hasKey(ch)) {
                tempNode->setChild(ch, new TrieNode());
            }
            tempNode = tempNode->getChild(ch);
        }
    }
    
    bool checkPrefix(string& prefix) {
        TrieNode* tempNode = rootHead;
        for (char ch : prefix) {
            if (!tempNode->hasKey(ch)) {
                return false;
            }
            tempNode = tempNode->getChild(ch);
        }
        return true;
    }
};
    
class Solution {
public:
    int calculatePairs(vector<string>& words) {
        int size = words.size();
        int totalPairs = 0;
    
        for (int i = 0; i < size; i++) {
            TrieStructure prefixTrie, reversedTrie;
    
            prefixTrie.addWord(words[i]);
    
            string reversedWord = words[i];
            reverse(reversedWord.begin(), reversedWord.end());
            reversedTrie.addWord(reversedWord);
    
            for (int j = 0; j < i; j++) {
                if (words[j].length() > words[i].length()) continue;
    
                string preWord = words[j];
                string revPreWord = preWord;
                reverse(revPreWord.begin(), revPreWord.end());
    
                if (prefixTrie.checkPrefix(preWord) &&
                    reversedTrie.checkPrefix(revPreWord)) {
                    totalPairs++;
                }
            }
        }
    
        return totalPairs;
    }
};