Vultr DocsLatest Content

Count Prefix and Suffix Pairs I

Updated on 21 May, 2025
Count Prefix and Suffix Pairs I header image

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

  • C++
  • Java
  • Python
cpp 
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;
    }
};

The provided C++ code implements a solution for counting the pairs of words where one word serves as a prefix and the reversed version of another word serves as a suffix. The implementation involves a data structure called a Trie, or prefix tree, which efficiently handles prefix queries and insertions.

Here’s how the solution is structured:

  • TrieNode: Defines the individual nodes of a Trie, each containing an array of child nodes corresponding to each letter of the alphabet (a to z). Methods include checks for the existence of a key, getting a child node, and setting a child node.
  • TrieStructure: Manages the Trie operations, including adding words to the Trie and checking the presence of prefixes in the Trie.
  • Solution: Contains the method calculatePairs to determine the count of valid prefix-suffix pairs in the provided list of words. The algorithm works by:
    • Creating two tries for each word: one for the word itself and another for its reversed version.
    • Comparing each word's prefixes and reversed versions against previously processed words using the Trie structures to see if they match as described.

Within calculatePairs, the code iterates over each word, creates a Trie for it and its reverse, and then iteratively checks for each previous word if it can be a prefix or reversed suffix. The total count of such valid pairs is then returned.

This approach optimizes the matching process, employing Tries to effectively handle prefix checks over straightforward string manipulation methods, thus leaning on Tries for more performance-efficient prefix lookups.

java 
class TrieNode {
    private TrieNode[] children = new TrieNode[26];

    // Method to check the presence of a character in the trie node
    public boolean checkCharacter(char character) {
        return children[character - 'a'] != null;
    }

    // Method to insert a node in trie
    public void insertNode(char character, TrieNode newNode) {
        children[character - 'a'] = newNode;
    }

    // Method to get the node connected to a given character
    public TrieNode getChildNode(char character) {
        return children[character - 'a'];
    }
}

class DictionaryTree {

    private TrieNode rootNode;

    public DictionaryTree() {
        rootNode = new TrieNode();
    }

    // Method to add a word into the dictionary tree
    public void addWord(String word) {
        TrieNode tempNode = rootNode;
        for (char character : word.toCharArray()) {
            if (!tempNode.checkCharacter(character)) {
                tempNode.insertNode(character, new TrieNode());
            }
            tempNode = tempNode.getChildNode(character);
        }
    }

    // Method to verify if the tree contains a node for a given prefix
    public boolean hasPrefix(String prefix) {
        TrieNode tempNode = rootNode;
        for (char character : prefix.toCharArray()) {
            if (!tempNode.checkCharacter(character)) {
                return false;
            }
            tempNode = tempNode.getChildNode(character);
        }
        return true;
    }
}

class Solution {

    public int calculatePrefSufPairs(String[] words) {
        int totalWords = words.length;
        int result = 0;

        for (int i = 0; i < totalWords; i++) {
            DictionaryTree prefixTree = new DictionaryTree();
            DictionaryTree suffixTree = new DictionaryTree();

            prefixTree.addWord(words[i]);

            String reversedWord = new StringBuilder(words[i]).reverse().toString();
            suffixTree.addWord(reversedWord);

            for (int j = 0; j < i; j++) {
                if (words[j].length() > words[i].length()) continue;

                String currentPrefix = words[j];
                String reversedCurrentPrefix = new StringBuilder(currentPrefix).reverse().toString();

                if (prefixTree.hasPrefix(currentPrefix) && suffixTree.hasPrefix(reversedCurrentPrefix)) {
                    result++;
                }
            }
        }
        return result;
    }
}

This Java solution implements a method to count the pairs of words where one word is a prefix and its reverse is a suffix of another word. Here's how the solution is structured:

Overview of Classes and Methods

  • TrieNode Class

    • Manages individual nodes within a trie data structure.
    • Features insertion and query operations to handle character nodes efficiently.

  • DictionaryTree Class

    • Utilizes the TrieNode class to build a trie for storing words and prefixes.
    • Supports methods for adding entire words and checking the presence of prefixes.

  • Solution Class

    • Calculates pairs using two instances of DictionaryTree; one for prefixes and another for suffixes (which store reversed words).
    • The core method, calculatePrefSufPairs, iterates over a list of words and utilizes the DictionaryTrees to count valid prefix-suffix pairs.

Procedure Within calculatePrefSufPairs

  1. Initialize counters and iterate through each word in the input array.
  2. For each word, construct a new trie for prefixes and another for reversed words as suffixes.
  3. Add the current word to the prefix trie and its reversed version to the suffix trie.
  4. Iterate over previous words to determine if any of them, or their reversals, can be a prefix to the word in the main loop.
  5. If conditions are met, increment the result counter.

Key Points

  • Each word is processed in regards to all previously processed words, checking possible prefix conditions in both normal and reversed orders.
  • Utilizes the efficient prefix tree (trie) structure for fast prefix checking and insert operations.
  • The solution provides a method for preprocessing words into a data structure that allows quick query operations, essential for reducing runtime in prefix-suffix checking scenarios.

Ultimately, this Java program efficiently maps and processes words to find specific relational pairs using advanced data structuring and string manipulation techniques.

python 
class TreeNode:
    def __init__(self):
        self.children = [None] * 26

    def has_char(self, char: str) -> bool:
        return self.children[ord(char) - ord('a')] is not None

    def set_node(self, char: str, node: "TreeNode") -> None:
        self.children[ord(char) - ord('a')] = node

    def get_node(self, char: str) -> "TreeNode":
        return self.children[ord(char) - ord('a')]

class PrefixTree:
    def __init__(self):
        self.base = TreeNode()

    def add_word(self, word: str) -> None:
        current_node = self.base
        for char in word:
            if not current_node.has_char(char):
                current_node.set_node(char, TreeNode())
            current_node = current_node.get_node(char)

    def check_prefix(self, prefix: str) -> bool:
        current_node = self.base
        for char in prefix:
            if not current_node.has_char(char):
                return False
            current_node = current_node.get_node(char)
        return True

class Solution:
    def evaluatePrefixSuffixPairs(self, word_list: List[str]) -> int:
        length = len(word_list)
        pair_count = 0

        for i in range(length):
            preTrie = PrefixTree()
            sufTrie = PrefixTree()

            preTrie.add_word(word_list[i])
            reversed_word = word_list[i][::-1]
            sufTrie.add_word(reversed_word)

            for j in range(i):
                if len(word_list[j]) > len(word_list[i]):
                    continue

                word_prefix = word_list[j]
                reversed_prefix = word_prefix[::-1]

                if preTrie.check_prefix(word_prefix) and sufTrie.check_prefix(reversed_prefix):
                    pair_count += 1

        return pair_count

In the given Python code snippet for solving the "Count Prefix and Suffix Pairs I" problem, two custom data structures, TreeNode and PrefixTree (a form of trie), are implemented to efficiently handle prefix and suffix checks for a list of words.

  • TreeNode: This class initializes nodes with an array of 26 elements representing each letter of the alphabet. The methods has_char, set_node, and get_node allow checking the existence of a character, setting a node, and getting a node corresponding to a character, respectively.
  • PrefixTree: Constructed using the TreeNode, this class includes methods for adding words and checking prefixes.
    • add_word method adds a word to the trie.
    • check_prefix verifies whether a given prefix exists in the trie starting from the base node.

The Solution class's method evaluatePrefixSuffixPairs takes a list of words and counts the valid prefix and suffix pairs where one word is a prefix of another and, at the same time, its reverse is a suffix of the same word. For efficiency:

  • Two separate tries (prefix and suffix) are constructed for each word.
  • The trie for suffix checks is built using the reverse of the word.
  • Only pairs where the second word is shorter than or equal to the first word are considered, reducing unnecessary computations.

The flow includes iterating through each word, initializing fresh prefix and suffix tries, and checking against earlier words. If both prefix and suffix conditions are satisfied, the pair count is incremented. This implementation allows checking for prefix and suffix relationships in an optimized manner using trie data structures.

Comments

No comments yet.