Prefix Relation Pairs
MediumTries · Uber
You are given two lists of non-empty lowercase strings, left and right.
A pair (i, j) is prefix-related if left[i] is a prefix of right[j] or right[j] is a prefix of left[i]. A string counts as a prefix of itself, so equal strings are prefix-related.
Return the number of prefix-related pairs (i, j) with 0 <= i < left.length and 0 <= j < right.length.
- Each pair of positions is counted at most once, even when both directions hold (equal strings).
- Duplicate strings are separate entries: every position counts.
The lists can be large, so comparing every string in left with every string in right is too slow.
Example 1
- Input:
- left = ["app", "apple", "bat"], right = ["apple", "ap", "b", "cat"]
- Output:
- 5
- Explanation
apppairs withapple(it is a prefix of it) and withap(which is a prefix of it).applepairs withappleandap.batpairs withb. Nothing pairs withcat, for 5 pairs in total.
Example 2
- Input:
- left = ["a", "a"], right = ["a", "ab"]
- Output:
- 4
- Explanation
- Each of the two
aentries inleftis prefix-related to bothaandab, giving 2 * 2 = 4 pairs.
Example 3
- Input:
- left = ["abc"], right = ["abd", "bc"]
- Output:
- 0
- Explanation
abcandabdshareabbut neither is a prefix of the other, andbcdoes not startabc.
Constraints
0 <= left.length, right.length <= 2 * 10^41 <= left[i].length, right[j].length- The total length of all strings is at most
2 * 10^5 - Strings contain only lowercase English letters