3045. Count Prefix and Suffix Pairs II LeetCode Solution
In this guide, you will get 3045. Count Prefix and Suffix Pairs II LeetCode Solution with the best time and space complexity. The solution to Count Prefix and Suffix Pairs II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Count Prefix and Suffix Pairs II
You are given a 0-indexed string array words.
Let’s define a boolean function isPrefixAndSuffix that takes two strings, str1 and str2:
isPrefixAndSuffix(str1, str2) returns true if str1 is both a prefix and a suffix of str2, and false otherwise.
For example, isPrefixAndSuffix(“aba”, “ababa”) is true because “aba” is a prefix of “ababa” and also a suffix, but isPrefixAndSuffix(“abc”, “abcd”) is false.
Return an integer denoting the number of index pairs (i, j) such that i < j, and isPrefixAndSuffix(words[i], words[j]) is true.
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 <= 105
1 <= words[i].length <= 105
words[i] consists only of lowercase English letters.
The sum of the lengths of all words[i] does not exceed 5 * 105.
Complexity Analysis
Time Complexity: O(\Sigma |\texttt{words[i]}|)
Space Complexity: O(\Sigma |\texttt{words[i]}|)
3045. Count Prefix and Suffix Pairs II LeetCode Solution in C++
struct TrieNode {
unordered_map<int, shared_ptr<TrieNode>> children;
int count = 0;
};
class Trie {
public:
int insert(const string& word) {
const int n = word.length();
int count = 0;
shared_ptr<TrieNode> node = root;
for (int i = 0; i < n; ++i) {
const int j = hash(word[i], word[n - 1 - i]);
if (node->children[j] == nullptr)
node->children[j] = make_shared<TrieNode>();
node = node->children[j];
count += node->count;
}
++node->count;
return count;
}
private:
shared_ptr<TrieNode> root = make_shared<TrieNode>();
static int hash(char prefix, char suffix) {
return 26 * (prefix - 'a') + (suffix - 'a');
}
};
class Solution {
public:
// Same as 3042. Count Prefix and Suffix Pairs I
long long countPrefixSuffixPairs(vector<string>& words) {
long ans = 0;
Trie trie;
for (const string& word : words)
ans += trie.insert(word);
return ans;
}
}; /* code provided by PROGIEZ */
3045. Count Prefix and Suffix Pairs II LeetCode Solution in Java
class TrieNode {
Map<Integer, TrieNode> children = new HashMap<>();
int count = 0;
}
class Trie {
public int insert(final String word) {
final int n = word.length();
int count = 0;
TrieNode node = root;
for (int i = 0; i < n; ++i) {
final char prefix = word.charAt(i);
final char suffix = word.charAt(n - 1 - i);
final int key = (prefix - 'a') * 26 + (suffix - 'a');
node.children.putIfAbsent(key, new TrieNode());
node = node.children.get(key);
count += node.count;
}
++node.count;
return count;
}
private TrieNode root = new TrieNode();
}
class Solution {
// Same as 3045. Count Prefix and Suffix Pairs II
public long countPrefixSuffixPairs(String[] words) {
long ans = 0;
Trie trie = new Trie();
for (final String word : words)
ans += trie.insert(word);
return ans;
}
} // code provided by PROGIEZ
3045. Count Prefix and Suffix Pairs II LeetCode Solution in Python
class TrieNode:
def __init__(self):
self.children: dict[tuple[str, str], TrieNode] = {}
self.count = 0
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> int:
node = self.root
count = 0
for i, prefix in enumerate(word):
suffix = word[-1 - i]
node = node.children.setdefault((prefix, suffix), TrieNode())
count += node.count
node.count += 1
return count
class Solution:
# Same as 3045. Count Prefix and Suffix Pairs II
def countPrefixSuffixPairs(self, words: list[str]) -> int:
trie = Trie()
return sum(trie.insert(word) for word in words) # code by PROGIEZ
