The Isogram problem

Here’s my implementation [it’s actually part of a class called FWord that defines the word so that all testing on the word happens in that object].

There are a couple of points I’d add to any discussion on algorithmic efficiency.

  1. Code only needs to be made more efficient if it’s in a time-critical function where there’s a bottleneck. There’s no point wasting time writing a perfect function that has all the time in the world to excecute! Optimisation can take up a lot of time, and complex algorithms aren’t always easy to understand. Writing code that other people can read and maintain pays off, especially if at some point you end up working in a team!

  2. Efficiency savings that work by eliminating things like multiple tests or assignments aren’t usually as efficient as people think, especially given that most modern optimising compilers will do those optimisations for you anyway!

All my books are a bit old, but Robert Sedgwick - Algorithms in C++ is still a great reference [Implements in C++ and I belive has been updated] and Practical Algorithms for Programers is also a good book which I personally found helpful when I started out [implements in c] and useful for anyone who wants to understand both how algorithm efficiency is measured and how their implemented using basic data structures!

A lot of things like maps and lists are now implemented in the standard libraries, but I would urge anyone who wants a better understanding of how they work to implement thier own, if just for fun :slight_smile: Understanding how a hash table works can help you understand why, how, and when it should be used!

Anyway, here’s some code I came up with to throw into the ring :wink:
{
/* Create a direct 1 to 1 mapping using the smallest and least complex data type. A hash table would require
a key value pair, so would defeate the purpose of the excersise by introducing un necicary complxity. The
down side is that this might not scale for any other aplications, or indeed could cause problems on other
platrforms as we’re directly accessing a raw array of 8 bit chars */

char map[127];

// make sure the map has no random values before using it [0 isn't used in ascii as a character] 
std::memset(map, 0, 127);

/* get the length of the string so we don't need to do it more than once. 
   We can't rely on std::string to store the value */
int len = mWord.length();

// Iterate throgh the map testing each letter
for(int idx=0; idx <= len; idx++ )
{
	// We could bypass the asignment, but the compiler will take care of that optimisation for us
	char c = mWord[idx];
	if (map[c] > 0) { 
		// If the entry greater than 0 it's happened before, so can't be an isogram
		return false;
	} else {
		/* We only care that it's greater than 0, though arguably the compiler will 
		   optimize incrementation to the same degree as asignment */
		map[c]=1;
	}
}

return true;

}

Privacy & Terms