3045. Count Prefix and Suffix Pairs II

SourceWeekly Contest 385 Q4DifficultyHardRating2327

Description

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 <= 10⁵
1 <= words[i].length <= 10⁵
words[i] consists only of lowercase English letters.
The sum of the lengths of all words[i] does not exceed 5 * 10⁵.

Solutions

Solution 1: Trie

Thinking

\(n\) and the total length reach \(10^5\), so part I’s double loop is gone and the trie from its second method is required.

Pairs \((s[i], s[m-1-i])\) are the edges. Inserting in input order, the counts already on the path are earlier strings for which the current one is a prefix and a suffix.

We increment the terminal node afterwards so that only pairs with \(i<j\) are counted.

We can treat each string \(s\) in the string array as a list of character pairs, where each character pair \((s[i], s[m - i - 1])\) represents the \(i\)th character pair of the prefix and suffix of string \(s\).

We can use a trie to store all the character pairs, and then for each string \(s\), we search for all the character pairs \((s[i], s[m - i - 1])\) in the trie, and add their counts to the answer.

The time complexity is \(O(n \times m)\), and the space complexity is \(O(n \times m)\). Here, \(n\) and \(m\) are the lengths of words and the maximum length of the strings, respectively.

Python3JavaC++GoTypeScript

class Node:
    __slots__ = ["children", "cnt"]

    def __init__(self):
        self.children = {}
        self.cnt = 0


class Solution:
    def countPrefixSuffixPairs(self, words: List[str]) -> int:
        ans = 0
        trie = Node()
        for s in words:
            node = trie
            for p in zip(s, reversed(s)):
                if p not in node.children:
                    node.children[p] = Node()
                node = node.children[p]
                ans += node.cnt
            node.cnt += 1
        return ans

class Node {
    Map<Integer, Node> children = new HashMap<>();
    int cnt;
}

class Solution {
    public long countPrefixSuffixPairs(String[] words) {
        long ans = 0;
        Node trie = new Node();
        for (String s : words) {
            Node node = trie;
            int m = s.length();
            for (int i = 0; i < m; ++i) {
                int p = s.charAt(i) * 32 + s.charAt(m - i - 1);
                node.children.putIfAbsent(p, new Node());
                node = node.children.get(p);
                ans += node.cnt;
            }
            ++node.cnt;
        }
        return ans;
    }
}

class Node {
public:
    unordered_map<int, Node*> children;
    int cnt;

    Node()
        : cnt(0) {}
};

class Solution {
public:
    long long countPrefixSuffixPairs(vector<string>& words) {
        long long ans = 0;
        Node* trie = new Node();
        for (const string& s : words) {
            Node* node = trie;
            int m = s.length();
            for (int i = 0; i < m; ++i) {
                int p = s[i] * 32 + s[m - i - 1];
                if (node->children.find(p) == node->children.end()) {
                    node->children[p] = new Node();
                }
                node = node->children[p];
                ans += node->cnt;
            }
            ++node->cnt;
        }
        return ans;
    }
};

type Node struct {
    children map[int]*Node
    cnt      int
}

func countPrefixSuffixPairs(words []string) (ans int64) {
    trie := &Node{children: make(map[int]*Node)}
    for _, s := range words {
        node := trie
        m := len(s)
        for i := 0; i < m; i++ {
            p := int(s[i])*32 + int(s[m-i-1])
            if _, ok := node.children[p]; !ok {
                node.children[p] = &Node{children: make(map[int]*Node)}
            }
            node = node.children[p]
            ans += int64(node.cnt)
        }
        node.cnt++
    }
    return
}

class Node {
    children: Map<number, Node> = new Map<number, Node>();
    cnt: number = 0;
}

function countPrefixSuffixPairs(words: string[]): number {
    let ans: number = 0;
    const trie: Node = new Node();
    for (const s of words) {
        let node: Node = trie;
        const m: number = s.length;
        for (let i: number = 0; i < m; ++i) {
            const p: number = s.charCodeAt(i) * 32 + s.charCodeAt(m - i - 1);
            if (!node.children.has(p)) {
                node.children.set(p, new Node());
            }
            node = node.children.get(p)!;
            ans += node.cnt;
        }
        ++node.cnt;
    }
    return ans;
}

3045. Count Prefix and Suffix Pairs II

Description

Solutions

Solution 1: Trie

Comments