Friday, February 4, 2011

Print first unique character in a stirng

Precondition:

Assume only ascii characters.

Algorithm:

step 1: Declare c[128] = {0}
step 2: for each element in string s,
stpe 3: increment *(c+(int)s[i]])
step 4: end for
step 5: for each element in c
step 6: if count is 1, break and (char)i is the unique char
step 7: end for

step 8: if i == 128, no unique char

Code:



char find_unique(char *s){
 
 int a[128] = {0};
 char c;


 // count the number of occurances of each element in the array
 while( c = *s++ ){
  a[c]++;
 }
 
 // check for the char with exactly one occurance
 for( i=0;i<128;i++)
  if( a[i] == 1)
   break;  
 
 // means no element is unique, return null
 if( i == 128 )
  return '\0';
 
 return (char)i;
 
}

No comments :

Post a Comment