exercism

commit 37181b0c198fd5a1dfcdcafa42069ade7e610aa5
parent c5d1d0199bc0df1baef24fe1b79fa47f653062d9
Author: dwrz <dwrz@dwrz.net>
Date:   Sun, 24 Feb 2019 12:59:43 +0000

Optimize c/isogram/is_isogram to use map, not inner loop

Diffstat:
M
c/isogram/src/isogram.c
 | 
22
++++++++--------------

1 file changed, 8 insertions(+), 14 deletions(-)
diff --git a/c/isogram/src/isogram.c b/c/isogram/src/isogram.c
@@ -33,21 +33,15 @@ bool is_symbol_char(char c) {
 bool is_isogram(const char phrase[]) {
   if (phrase == NULL) { return false; }
   if (length(phrase) == 0) { return true; }
-  // Lowercase the phrase.
-  // We make a copy, since the input is constant.
-  char lower_phrase[(length(phrase))];
-  copy_phrase(phrase, lower_phrase);
-  lowercase_phrase(lower_phrase);
-  // Check if the lowercased phrase is an isogram.
-  for (int i = 0; i < length(lower_phrase); i++) {
-    if (is_symbol_char(lower_phrase[i])) { continue; } // Ignore non-alpha chars.
-    for (int j = 0; j < length(lower_phrase); j++) {
-      if (is_symbol_char(lower_phrase[j])) { continue; }
-      if (j == i) { continue; }
-      if (lower_phrase[i] == lower_phrase[j]) {
-        return false;
-      }
+  // There are 26 lowercased ASCII alpha chars.
+  // We can use 26 indexes to keep track of each one.
+  char char_map[26] = { 0 };
+  for (int i = 0; i < length(phrase); i++) {
+    if (is_symbol_char(phrase[i])) { continue; } // Ignore non-alpha chars.
+    if (char_map[lowercase(phrase[i]) - 97] != 0) {
+      return false;
     }
+    char_map[lowercase(phrase[i]) - 97]++;
   }
   return true;
 }