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 | |
parent | 34a6791c29e4c23dd299327a33247a77d39cc681 (diff) | |
download | leetcode-b5c87065a4c77cc960dd1f852ccd6aba1185e11f.tar.gz leetcode-b5c87065a4c77cc960dd1f852ccd6aba1185e11f.zip |
-rw-r--r-- | find_restaurant_arr_rem_anagram.c | 55 | ||||
-rw-r--r-- | find_restaurant_arr_rem_anagram.py | 36 |
2 files changed, 91 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); +} diff --git a/find_restaurant_arr_rem_anagram.py b/find_restaurant_arr_rem_anagram.py new file mode 100644 index 0000000..2cb4b8a --- /dev/null +++ b/find_restaurant_arr_rem_anagram.py @@ -0,0 +1,36 @@ +# 2273. Find Resultant Array After Removing Anagrams + +""" +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. +""" + + +class Solution(object): + def anagram(self, s, t): + return sorted(s) == sorted(t) + + def removeAnagrams(self, words): + """ + :type words: List[str] + :rtype: List[str] + """ + ans = [] + for i in words: + if ans and self.anagram(ans[-1], i): + continue + ans.append(i) + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.removeAnagrams(words=["abba", "baba", "bbaa", "cd", "cd"])) + print(obj.removeAnagrams(words=["a", "b", "c", "d", "e"])) |