aboutsummaryrefslogtreecommitdiff
path: root/repeated_dna_sequences.c
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-08-30 18:16:42 -0600
committerJack Sangdahl <[email protected]>2024-08-30 18:16:42 -0600
commit48154c27a07e1216ae206613e58393aa853e6f38 (patch)
treefe90d2092eac3996ae07c7008690f05e11164c82 /repeated_dna_sequences.c
parentaccfdfe3a52d62bee9b2c24dece6f2b613ceeb7c (diff)
downloadleetcode-48154c27a07e1216ae206613e58393aa853e6f38.tar.gz
leetcode-48154c27a07e1216ae206613e58393aa853e6f38.zip
187. repeated dna sequences
Diffstat (limited to 'repeated_dna_sequences.c')
-rw-r--r--repeated_dna_sequences.c98
1 files changed, 98 insertions, 0 deletions
diff --git a/repeated_dna_sequences.c b/repeated_dna_sequences.c
new file mode 100644
index 0000000..5c7fdcf
--- /dev/null
+++ b/repeated_dna_sequences.c
@@ -0,0 +1,98 @@
+// 187. Repeated DNA Sequences
+#include "leetcode.h"
+
+/*
+ * the dna sequence is composed of a series of nucleotides abbreviated as A, C,
+ * G, and T. when studying dna it is useful to identify repeated sequences
+ * within the dna. given a string 's' that represents a dna sequence, return all
+ * the 10 letter long sequences (substrings) that occur more than once in a dna
+ * molecule. you may return the answer in any order
+ */
+
+int cmp(const void *a, const void *b) { return *(int *)a - *(int *)b; }
+
+int val(char c) {
+ switch (c) {
+ case 'A':
+ return 0;
+ case 'C':
+ return 1;
+ case 'G':
+ return 2;
+ case 'T':
+ return 3;
+ default:
+ return -1;
+ }
+}
+
+void decode(char *s, int val) {
+ int i, rem;
+ s[10] = '\0';
+ for (i = 9; i >= 0; --i) {
+ rem = val % 4;
+ val /= 4;
+ switch (rem) {
+ case 0:
+ s[i] = 'A';
+ break;
+ case 1:
+ s[i] = 'C';
+ break;
+ case 2:
+ s[i] = 'G';
+ break;
+ case 3:
+ s[i] = 'T';
+ break;
+ }
+ }
+}
+
+char **findRepeatedDnaSequences(char *s, int *returnSize) {
+ int stk0[100000], sp0 = 0, stk1[100000], sp1 = 0, n = strlen(s), code = 0;
+ if (n < 10) {
+ *returnSize = 0;
+ return NULL;
+ }
+ for (int i = 0; i < 10; ++i)
+ code = 4 * code + val(s[i]);
+ stk0[sp0++] = code;
+ for (int i = 0; i < n - 10; ++i) {
+ code = (code & 0x3FFFF) * 4 + val(s[i + 10]);
+ stk0[sp0++] = code;
+ }
+ qsort(stk0, sp0, sizeof(int), cmp);
+ for (int i = 0, j; i < sp0 - 1; ++i)
+ if (stk0[i] == stk0[i + 1]) {
+ stk1[sp1++] = stk0[i];
+ for (j = i + 1; j < sp0 && stk0[i] == stk0[j]; ++j)
+ ;
+ i = j - 1;
+ }
+ char **ans = (char **)malloc(sp1 * sizeof(char *));
+ for (int i = 0; i < sp1; ++i) {
+ ans[i] = (char *)malloc(11 * sizeof(char));
+ decode(ans[i], stk1[i]);
+ }
+ *returnSize = sp1;
+ return ans;
+}
+
+int main() {
+ char *s1 = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT", *s2 = "AAAAAAAAAAAAA";
+ int rs1, rs2;
+ char **frds1 = findRepeatedDnaSequences(s1, &rs1);
+ char **frds2 = findRepeatedDnaSequences(s2, &rs2);
+ for (int i = 0; i < rs1; i++) {
+ printf("%s ", frds1[i]); // expect: ["AAAAACCCCC","CCCCCAAAAA"]
+ free(frds1[i]);
+ }
+ printf("\n");
+ for (int i = 0; i < rs2; i++) {
+ printf("%s ", frds2[i]); // expect: ["AAAAAAAAAA"]
+ free(frds2[i]);
+ }
+ printf("\n");
+ free(frds1), free(frds2);
+}