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[] cin, int[] chars, int[] unique) { for (int j = 0; j < cin.Length; j++) { for (int k = 0; k < unique.Length; k++) 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[] chars, int a) { for (int i = 0; i < chars.Length; i++) 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 = 0; i < u.Length; i++) if (u[i] > 1) return 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(chars, a); FillArray(cin, chars, unique); Console.WriteLine("The string\"{0}\" is unique? {1}", inp, isUnique(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 = 0; i < t.Length; i++) { for (int j = 0; j < t.Length; j++) { 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