diff options
author | Jack Sangdahl <[email protected]> | 2025-05-15 22:00:26 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-05-15 22:00:26 -0600 |
commit | 9b6473451c15a328a71f11cdf69ff36379e4ef15 (patch) | |
tree | 47aa535a71d2201e0e6267f6fd37afe38a62d15f | |
parent | 669b7bafe18ed3ebc31532766c489d0908882d05 (diff) | |
download | leetcode-9b6473451c15a328a71f11cdf69ff36379e4ef15.tar.gz leetcode-9b6473451c15a328a71f11cdf69ff36379e4ef15.zip |
2901. longest unequal adjacent groups subsequence 2
-rw-r--r-- | longest_unequal_adjacent_group2.c | 116 | ||||
-rw-r--r-- | longest_unequal_adjacent_group2.py | 50 |
2 files changed, 166 insertions, 0 deletions
diff --git a/longest_unequal_adjacent_group2.c b/longest_unequal_adjacent_group2.c new file mode 100644 index 0000000..9ccfe43 --- /dev/null +++ b/longest_unequal_adjacent_group2.c @@ -0,0 +1,116 @@ +// 2901. Longest Unequal Adjacent Groups Subsequence II +#include "leetcode.h" + +/* + * you are given a string array 'words' and an array 'groups', both arrays + * having length 'n'. the hamming distance between two strings of equal length + * is the number of positions at which the corresponding characters are + * different. you need to select the longest subsequence from an array of + * indices such that for the subsequence denoted as '[i0, i1, ..., ik-1]' having + * length 'k', the following holds true: for adjacent indices in the subsequence + * their corresponding groups are unequal. 'words[i]' and 'words[i + 1]' are + * equal in length and the haming distance between them is 1. return a string + * array containing the words corresponding to the indices in order in the + * selected subsequence. if there are multiple, return any of them. + */ + +struct pattern { + uint64_t pat; + int idx; +}; + +char **getWordsInLongestSubsequence(char **words, int wordsSize, int *groups, + int groupsSize, int *returnSize) { + int n = wordsSize; + if (!n) { + *returnSize = 0; + return NULL; + } + uint64_t *codes = (uint64_t *)malloc(n * sizeof(uint64_t)); + for (int i = 0; i < n; ++i) { + uint64_t curr = 0; + for (int j = 0; words[i][j]; ++j) + curr |= (uint64_t)(words[i][j - 1] - 'a') << (5 * j); + codes[i] = curr; + } + int *dp = (int *)malloc(n * sizeof(int)), + *prev = (int *)malloc(n * sizeof(int)); + for (int i = 0; i < n; ++i) { + dp[i] = 1; + prev[i] = -1; + } + int max_len = 1, max_idx = 0; + struct pattern *p[11][11] = {{0}}; + int sizes[11][11] = {0}, caps[11][11] = {0}; + for (int i = 0; i < n; ++i) { + int m = strlen(words[i]), curr_group = groups[i]; + uint64_t curr_code = codes[i]; + for (int j = 0; j < m; ++j) { + if (!caps[m][j]) { + caps[m][j] = 16; + p[m][j] = (struct pattern *)malloc(caps[m][j] * sizeof(struct pattern)); + sizes[m][j] = 0; + } + } + int best = 1, bp = -1; + for (int j = 0; j < m; ++j) { + uint64_t mask = ~((uint64_t)31 << (5 * j)), + curr_pattern = curr_code & mask; + struct pattern *arr = p[m][j]; + int curr_size = sizes[m][j]; + for (int k = 0; k < curr_size; ++k) { + if (arr[k].pat == curr_pattern) { + int idx = arr[k].idx; + if (groups[idx] != curr_group && dp[idx] + 1 > best) { + best = dp[idx] + 1; + bp = idx; + } + } + } + } + dp[i] = best; + prev[i] = bp; + if (best > max_len) { + max_len = best; + max_idx = i; + } + for (int j = 0; j < m; ++j) { + uint64_t mask = ~((uint64_t)31 << (5 * j)), + curr_pattern = curr_code & mask; + if (sizes[m][j] == caps[m][j]) { + caps[m][j] *= 2; + p[m][j] = (struct pattern *)realloc( + p[m][j], caps[m][j] * sizeof(struct pattern)); + } + p[m][j][sizes[m][j]].pat = curr_pattern; + p[m][j][sizes[m][j]].idx = i; + sizes[m][j]++; + } + } + char **tmp = (char **)malloc(max_len * sizeof(char *)); + int cnt = 0; + for (int i = max_idx; i != 1; i = prev[i]) + tmp[cnt++] = strdup(words[i]); + char **ans = (char **)malloc(cnt * sizeof(char *)); + for (int i = 0; i < cnt; i++) + ans[i] = tmp[cnt - 1 - i]; + *returnSize = cnt; + return ans; +} + +int main() { + char *w1[] = {"bab", "dab", "cab"}, *w2[] = {"a", "b", "c", "d"}; + int g1[] = {1, 2, 2}, g2[] = {1, 2, 3, 4}, rs1, rs2; + char **gwils1 = getWordsInLongestSubsequence((char **)w1, ARRAY_SIZE(w1), g1, + ARRAY_SIZE(g1), &rs1); + char **gwils2 = getWordsInLongestSubsequence((char **)w2, ARRAY_SIZE(w2), g2, + ARRAY_SIZE(g2), &rs2); + for (int i = 0; i < rs1; i++) + printf("%s ", gwils1[i]); // expect: bab cab + printf("\n"); + for (int i = 0; i < rs2; i++) + printf("%s ", gwils2[i]); // expect: a b c d + printf("\n"); + free(gwils1); + free(gwils2); +} diff --git a/longest_unequal_adjacent_group2.py b/longest_unequal_adjacent_group2.py new file mode 100644 index 0000000..44255d1 --- /dev/null +++ b/longest_unequal_adjacent_group2.py @@ -0,0 +1,50 @@ +# 2901. Longest Unequal Adjacent Groups Subsequence II + +""" +you are given a string array 'words' and an array 'groups', both arrays +having length 'n'. the hamming distance between two strings of equal length +is the number of positions at which the corresponding characters are +different. you need to select the longest subsequence from an array of +indices such that for the subsequence denoted as '[i0, i1, ..., ik-1]' having +length 'k', the following holds true: for adjacent indices in the subsequence +their corresponding groups are unequal. 'words[i]' and 'words[i + 1]' are +equal in length and the haming distance between them is 1. return a string +array containing the words corresponding to the indices in order in the +selected subsequence. if there are multiple, return any of them. +""" + + +class Solution(object): + def getWordsInLongestSubsequence(self, words, groups): + """ + :type words: List[str] + :type groups: List[int] + :rtype: List[str] + """ + dp = [] + for i, j in zip(words, groups): + dp.append( + max( + ( + k + for a, b, k in zip(words, groups, dp) + if j != b and len(i) == len(a) and sum(map(ne, i, a)) < 2 + ), + key=len, + default=[], + ) + + [i] + ) + return max(dp, key=len) + + +if __name__ == "__main__": + obj = Solution() + print( + obj.getWordsInLongestSubsequence(words=["bab", "dab", "cab"], groups=[1, 2, 2]) + ) + print( + obj.getWordsInLongestSubsequence( + words=["a", "b", "c", "d"], groups=[1, 2, 3, 4] + ) + ) |