commit 69e611af083aca7118ae10a035e1971440dd440e
parent d8d12c24604d7ac3d5382998cc9550e503726d1e
Author: Jack Sangdahl <jack@pngu.org>
Date: Thu, 28 May 2026 08:12:29 -0600
3093. longest common suffix queries
Diffstat:
2 files changed, 181 insertions(+), 0 deletions(-)
diff --git a/longest_common_suffix_queries.c b/longest_common_suffix_queries.c
@@ -0,0 +1,116 @@
+// 3093. Longest Common Suffix Queries
+#include "leetcode.h"
+
+/*
+ * you are given two arrays of strings 'wordsContainer' and 'wordsQuery'. for
+ * each 'wordsQuery[i]', you need to find a string from 'wordsContainer' that
+ * has the longest common suffix with 'wordsQuery[i]'. if there are two or more
+ * string in 'wordsContainer' that share the longest common suffix, find the
+ * string that is the smallest in length. if there are two or more such strigs
+ * that have the same smallest length, find the one that occured earlier in
+ * 'wordsContainer'. return an array of integers 'ans' where 'ans[i]' is the
+ * index of the string in 'wordsContainer' that has the longest common suffix
+ * with 'wordsQuery[i]'.
+ */
+
+struct trie_node {
+ struct trie_node *children[26];
+ int min_len;
+ int idx;
+};
+
+struct trie_node *trie_node_init(void) {
+ struct trie_node *obj = (struct trie_node *)malloc(sizeof(struct trie_node));
+ for (int i = 0; i < 26; i++)
+ obj->children[i] = NULL;
+ obj->min_len = obj->idx = INT_MAX;
+ return obj;
+}
+
+void insert(struct trie_node *root, const char *s, int idx) {
+ int n = strlen(s);
+ struct trie_node *node = root;
+ if (n < node->min_len) {
+ node->min_len = n;
+ node->idx = idx;
+ }
+ for (int i = 0; i < n; i++) {
+ int curr = s[i] - 'a';
+ if (!node->children[curr])
+ node->children[curr] = trie_node_init();
+ node = node->children[curr];
+ if (n < node->min_len) {
+ node->min_len = n;
+ node->idx = idx;
+ }
+ }
+}
+
+int query(struct trie_node *root, const char *s) {
+ int n = strlen(s);
+ struct trie_node *node = root;
+ for (int i = 0; i < n; i++) {
+ int curr = s[i] - 'a';
+ if (node->children[curr])
+ node = node->children[curr];
+ else
+ break;
+ }
+ return node->idx;
+}
+
+void trie_node_free(struct trie_node *obj) {
+ for (int i = 0; i < 26; i++)
+ if (obj->children[i])
+ trie_node_free(obj->children[i]);
+ free(obj);
+}
+
+void reverse_string(char *s) {
+ int n = strlen(s);
+ for (int i = 0, j = n - 1; i < j; i++, j--) {
+ char tmp = s[i];
+ s[i] = s[j];
+ s[j] = tmp;
+ }
+}
+
+int *stringIndices(char **wordsContainer, int wordsContainerSize,
+ char **wordsQuery, int wordsQuerySize, int *returnSize) {
+ struct trie_node *root = trie_node_init();
+ for (int i = 0; i < wordsContainerSize; i++) {
+ reverse_string(wordsContainer[i]);
+ insert(root, wordsContainer[i], i);
+ }
+ int *ans = (int *)malloc(wordsQuerySize * sizeof(int));
+ *returnSize = wordsQuerySize;
+ for (int i = 0; i < wordsQuerySize; i++) {
+ reverse_string(wordsQuery[i]);
+ ans[i] = query(root, wordsQuery[i]);
+ }
+ trie_node_free(root);
+ return ans;
+}
+
+int main() {
+ char *wc1[] = {"abcd", "bcd", "xbcd"};
+ char *wq1[] = {"cd", "bcd", "xyz"};
+ char *wc2[] = {"abcdefgh", "poiuygh", "ghghgh"};
+ char *wq2[] = {"gh", "acbfgh", "acbfegh"};
+ int r1[] = {1, 1, 1}, rs1;
+ int r2[] = {2, 0, 2}, rs2;
+ int *si1 = stringIndices(wc1, ARRAY_SIZE(wc1), wq1, ARRAY_SIZE(wq1), &rs1);
+ int *si2 = stringIndices(wc2, ARRAY_SIZE(wc2), wq2, ARRAY_SIZE(wq2), &rs2);
+ for (int i = 0; i < rs1; i++) {
+ printf("%d ", si1[i]);
+ assert(si1[i] == r1[i]);
+ }
+ printf("\n");
+ for (int i = 0; i < rs2; i++) {
+ printf("%d ", si2[i]);
+ assert(si2[i] == r2[i]);
+ }
+ printf("\n");
+ free(si1);
+ free(si2);
+}
diff --git a/longest_common_suffix_queries.py b/longest_common_suffix_queries.py
@@ -0,0 +1,65 @@
+# 3093. Longest Common Suffix Queries
+from typing import List
+
+"""
+you are given two arrays of strings 'wordsContainer' and 'wordsQuery'. for
+each 'wordsQuery[i]', you need to find a string from 'wordsContainer' that
+has the longest common suffix with 'wordsQuery[i]'. if there are two or more
+string in 'wordsContainer' that share the longest common suffix, find the
+string that is the smallest in length. if there are two or more such strigs
+that have the same smallest length, find the one that occured earlier in
+'wordsContainer'. return an array of integers 'ans' where 'ans[i]' is the
+index of the string in 'wordsContainer' that has the longest common suffix
+with 'wordsQuery[i]'.
+"""
+
+
+class trie_node:
+ def __init__(self):
+ self.children = {}
+ self.min_len = float("inf")
+ self.idx = float("inf")
+
+
+class Solution:
+ def stringIndices(
+ self, wordsContainer: List[str], wordsQuery: List[str]
+ ) -> List[int]:
+ root = trie_node()
+ for i, word in enumerate(wordsContainer):
+ n = len(word)
+ curr = root
+ if n < curr.min_len or (n == curr.min_len and i < curr.idx):
+ curr.min_len = n
+ curr.idx = i
+ for char in reversed(word):
+ if char not in curr.children:
+ curr.children[char] = trie_node()
+ curr = curr.children[char]
+ if n < curr.min_len or (n == curr.min_len and i < curr.idx):
+ curr.min_len = n
+ curr.idx = i
+ ans = []
+ for query in wordsQuery:
+ curr = root
+ for char in reversed(query):
+ if char not in curr.children:
+ break
+ curr = curr.children[char]
+ ans.append(curr.idx)
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.stringIndices(
+ wordsContainer=["abcd", "bcd", "xbcd"], wordsQuery=["cd", "bcd", "xyz"]
+ )
+ )
+ print(
+ obj.stringIndices(
+ wordsContainer=["abcdefgh", "poiuygh", "ghghgh"],
+ wordsQuery=["gh", "acbfgh", "acbfegh"],
+ )
+ )
