Show problems as
Classic problem #3093HardArrayStringTrie

Longest Common Suffix Queries

Real-world version: Best Match by Shared Ending
Tracked in this browser only
Read Longest Common Suffix Queries on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A catalogue is given as wordsContainer and a list of lookups as wordsQuery, both lists of lowercase words.

For each lookup, find the catalogue entry sharing the longest ending with it, where an ending means a run of characters at the very end of both words; sharing no ending at all counts as a shared ending of length zero. Break a tie on that length by taking the shorter catalogue entry, and break a remaining tie by taking the one listed earliest.

Return the position in the catalogue of the entry chosen for each lookup, in the order the lookups are given.

Examples

Example 1

Input
wordsContainer = ["crate", "grate", "plate", "late"], wordsQuery = ["slate", "ornate", "crate"]
Output
[3, 3, 0]

The lookup "slate" shares the ending "late" with both "plate" and "late", and the shorter of those wins. The lookup "ornate" shares only "ate", which the same three entries offer, so the shortest one wins again. The lookup "crate" shares all five characters with the entry at position 0.

Example 2

Input
wordsContainer = ["aa", "bb", "cc"], wordsQuery = ["dd", "aa"]
Output
[0, 0]

The lookup "dd" shares no ending with anything, so the tie-break falls back to the shortest entry and then the earliest, giving position 0. The lookup "aa" matches the entry at position 0 outright.

Example 3

Input
wordsContainer = ["abc", "abc", "abc"], wordsQuery = ["abc"]
Output
[0]

All three entries share the whole word and are the same length, so the earliest one is chosen.

Constraints

  • 1 <= wordsContainer.length <= 10^4
  • 1 <= wordsQuery.length <= 10^4
  • 1 <= wordsContainer[i].length <= 5 * 10^3
  • 1 <= wordsQuery[i].length <= 5 * 10^3
  • The total length of wordsContainer is at most 5 * 10^5
  • The total length of wordsQuery is at most 5 * 10^5
  • Every word consists of lowercase English letters only

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def string_indices(wordsContainer: list[str], wordsQuery: list[str]) -> list[int]:
Java
public int[] stringIndices(String[] wordsContainer, String[] wordsQuery)

More on the same topics