Wednesday, August 7, 2013

Does the string have unique characters?

Problem

We need an algorithm to determine if a string has all unique characters, none alphabet letters are exempted.

Solution

We will make three methods; the first shall return the alphabet letters; the second will fill an integer array with the frequency of occurrence of each letter; and the last method shall test for uniqueness of the string input.

/*********************************************************
       * Method FillArray shall fill the unique array with the *
       * with the frequency of occurence of each letter in the *
       * string cin                                            *
       * *******************************************************/
      private static void FillArray(char[] cinint[] charsint[] unique)
      {
         for (int j = 0j < cin.Lengthj++)
         {
            for (int k = 0k < unique.Lengthk++)
               if (cin[j== chars[k])
                  unique[k]++;
         }
      }
 
      /***********************************************
       * Method Get Alphabet will return an int array*
       * with all the lower case alphabet letters    *
       * *********************************************/
      private static int[] GetAlphabet(int[] charsint a)
      {
         for (int i = 0i < chars.Lengthi++)
            chars[i= a++;
         return chars;
      }
 
      /********************************************
       * The method isUnique shall test the unique*
       * int[] for occurences, if any of the      *
       * elements is bigger than 1, then the      *
       * string is not unique, and hence return   *
       * false                                    *
       * ******************************************/
      static bool isUnique(int[] u)
      {
         for (int i = 0i < u.Lengthi++)
            if (u[i> 1return false;
         return true;
      }


A sample input:

string inp = "abcd e f m".ToLower(); //input string
         char[] cin = inp.ToCharArray(); //string to array
         int[] chars = new int[26]; //alphabet letters
         int[] unique = new int[26]; //occurence array
         int a = 97//the letter a is '97' in ascii
 
         chars = GetAlphabet(charsa);
         FillArray(cincharsunique);
         Console.WriteLine("The string\"{0}\" is unique? {1}"inpisUnique(unique));

A sample output:



***

Can it be done with no extra data structures in place? Obviously:

private static bool IsStringUnique(char[] t)
      {
         int counter = 0;
         for (int i = 0i < t.Lengthi++)
         {
            for (int j = 0j < t.Lengthj++)
            {
               if (t[i== t[j])
                  counter++;
            }
            if (counter > 1)
               return false;
            counter = 0;
         }
         return true;
      }

Test input:

char[] t = "The quick brown fox".ToLower().Replace(" """).ToCharArray();
         bool b = IsStringUnique(t);
         Console.WriteLine("string is unique? {0}"b);

A sample output:



No comments:

Post a Comment