Solved

C# alogirthm help

Posted on 2013-12-12
4
183 Views
Last Modified: 2014-04-17
Hi
I have following algorithm written in Java to determine if a string has all unique characters or not.

Can anyone help me write this same in C# both with hashing and non hashing techniques?

public static boolean isUniqueChars2(String str) {
boolean[] char_set = new boolean[256];
 for (int i = 0; i < str.length(); i++) {
int val = str.charAt(i);
 if (char_set[val]) return false;
char_set[val] = true;
 }
 return true;
 }
0
Comment
Question by:Techsavy
  • 2
4 Comments
 
LVL 20

Expert Comment

by:Daniel Van Der Werken
ID: 39715048
This is how I would do it. It might not be the best or fastest or most efficient, but it works:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace IsUniqueChar
{
    class Program
    {
        static void Main(string[] args)
        {
            string inputString = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
            bool allAreUnique = ContainsAllUniqeCharacters(inputString);

            inputString = "AABCDEFGHIJKLMNOPQRSTUVWXYZ";
            allAreUnique = ContainsAllUniqeCharacters(inputString);
        }

        public static bool ContainsAllUniqeCharacters(string inputString)
        {
            bool allAreUnique = false;
            List<char> charList = new List<char>();
            char[] charArray = inputString.ToCharArray();
            foreach(char c in charArray)
            {
                if (!charList.Contains(c))
                {
                    charList.Add(c);
                }
            }
            if ( charList.Count == inputString.Length)
            {
                allAreUnique = true;
            }
            return allAreUnique;
        }
    }
}

Open in new window

0
 
LVL 29

Expert Comment

by:anarki_jimbel
ID: 39715325
Of course, hash algorithm is much faster:

        private void button8_Click(object sender, EventArgs e)
        {
            string inputString = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
            bool allAreUnique = ContainsAllUniqeCharacters(inputString);
            MessageBox.Show(allAreUnique.ToString());

            inputString = "AABCDEFGHIJKLMNOPQRSTUVWXYZ";
            allAreUnique = ContainsAllUniqeCharacters(inputString);
            MessageBox.Show(allAreUnique.ToString());
        }

        private bool ContainsAllUniqeCharacters(string inputString)
        {
            Dictionary<char, int> hash = new Dictionary<char, int>();

            foreach (char ch in inputString.ToCharArray())
            {
                if (hash.ContainsKey(ch))
                {
                    return false;
                }
                else
                {
                    hash.Add(ch, 1);
                }
            }
            return true;
        }

Open in new window

0
 
LVL 75

Accepted Solution

by:
käµfm³d   👽 earned 500 total points
ID: 39715683
I like the algorithm you have in the Java. IMO, it would beat anarki's Dictionary algorithm in terms of both memory usage and speed**. The C# version is almost identical:

public static bool isUniqueChars2(String str)
{
    bool[] char_set = new bool[256];

    for (int i = 0; i < str.Length; i++)
    {
        int val = str[i];
        if (char_set[val]) return false;
        char_set[val] = true;
    }

    return true;
}

Open in new window


I'd suggest modifying the array declaration though so that you're not using a hard-coded value for the size:

bool[] char_set = new bool[str.Length];

Open in new window


** You would need to analyze this at runtime, of course.
0
 
LVL 29

Expert Comment

by:anarki_jimbel
ID: 39715737
...it would beat anarki's Dictionary algorithm..

Definitely it will :). I even measured - at least, 10 times :).

The thing is that no one would care. You may do a check like:

if( inputString.Length >256)
   return false;

I.e. any string longer than 256 fails :). If you adjust this number (256)  by control chars it will be even smaller.

Does this matter will it take 20 ms or 2 ms to process then? :)
0

Featured Post

Master Your Team's Linux and Cloud Stack!

The average business loses $13.5M per year to ineffective training (per 1,000 employees). Keep ahead of the competition and combine in-person quality with online cost and flexibility by training with Linux Academy.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

IntroductionWhile developing web applications, a single page might contain many regions and each region might contain many number of controls with the capability to perform  postback. Many times you might need to perform some action on an ASP.NET po…
International Data Corporation (IDC) prognosticates that before the current the year gets over disbursing on IT framework products to be sent in cloud environs will be $37.1B.
Microsoft Active Directory, the widely used IT infrastructure, is known for its high risk of credential theft. The best way to test your Active Directory’s vulnerabilities to pass-the-ticket, pass-the-hash, privilege escalation, and malware attacks …
A short tutorial showing how to set up an email signature in Outlook on the Web (previously known as OWA). For free email signatures designs, visit https://www.mail-signatures.com/articles/signature-templates/?sts=6651 If you want to manage em…

789 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question