diff options
author | Jack Sangdahl <[email protected]> | 2025-10-12 18:31:26 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-10-12 18:31:26 -0600 |
commit | b5c87065a4c77cc960dd1f852ccd6aba1185e11f (patch) | |
tree | ad62e3e26c1328a5f24411e3638bbcf76cbaece6 /find_restaurant_arr_rem_anagram.c | |
parent | 34a6791c29e4c23dd299327a33247a77d39cc681 (diff) | |
download | leetcode-b5c87065a4c77cc960dd1f852ccd6aba1185e11f.tar.gz leetcode-b5c87065a4c77cc960dd1f852ccd6aba1185e11f.zip |
Diffstat (limited to 'find_restaurant_arr_rem_anagram.c')
-rw-r--r-- | find_restaurant_arr_rem_anagram.c | 55 |
1 files changed, 55 insertions, 0 deletions
diff --git a/find_restaurant_arr_rem_anagram.c b/find_restaurant_arr_rem_anagram.c new file mode 100644 index 0000000..2e2f1b3 --- /dev/null +++ b/find_restaurant_arr_rem_anagram.c @@ -0,0 +1,55 @@ +// 2273. Find Resultant Array After Removing Anagrams +#include "leetcode.h" + +/* + * you are given a 0-indexed string array 'words' where 'words[i]' consists of + * lowercase english letters. in one operation, select any index 'i' such that + * '0 < i < words.length' and 'words[i - 1]' and 'words[i]' are anagrams, and + * delete 'words[i]' from 'words'. keep performing this operation as long as yu + * can select an index that satisfies the conditions. return 'words' after + * performining all operations. it can be shown that selecting the indices for + * each operation in any arbitrary order will lead to the same result. an + * anagram is a word or phrase formed by rearranging the letters of a different + * word or phrase using all the original letters exactly once. + */ + +bool anagram(char *s, char *t) { + int hash[26] = {0}; + if (strlen(s) != strlen(t)) + return false; + for (int i = 0; i < strlen(s); i++) + hash[s[i] - 'a']++; + for (int i = 0; i < strlen(t); i++) + hash[t[i] - 'a']--; + for (int i = 0; i < 26; i++) + if (hash[i]) + return false; + return true; +} + +char **removeAnagrams(char **words, int wordsSize, int *returnSize) { + char **ans = (char **)calloc(wordsSize, sizeof(char *)); + int idx = 0; + ans[idx++] = words[0]; + for (int i = 1; i < wordsSize; i++) + if (!anagram(words[i - 1], words[i])) + ans[idx++] = words[i]; + *returnSize = idx; + return ans; +} + +int main() { + char *w1[] = {"abba", "baba", "bbaa", "cd", "cd"}, + *w2[] = {"a", "b", "c", "d", "e"}; + int rs1, rs2; + char **ra1 = removeAnagrams((char **)w1, ARRAY_SIZE(w1), &rs1); + char **ra2 = removeAnagrams((char **)w2, ARRAY_SIZE(w2), &rs2); + for (int i = 0; i < rs1; i++) + printf("%s ", ra1[i]); + printf("\n"); + for (int i = 0; i < rs2; i++) + printf("%s ", ra2[i]); + printf("\n"); + free(ra1); + free(ra2); +} |