Solved

C# alogirthm help

Posted on 2013-12-12
4
176 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

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

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

Suggested Solutions

This article is for Object-Oriented Programming (OOP) beginners. An Interface contains declarations of events, indexers, methods and/or properties. Any class which implements the Interface should provide the concrete implementation for each Inter…
Performance in games development is paramount: every microsecond counts to be able to do everything in less than 33ms (aiming at 16ms). C# foreach statement is one of the worst performance killers, and here I explain why.
Windows 10 is mostly good. However the one thing that annoys me is how many clicks you have to do to dial a VPN connection. You have to go to settings from the start menu, (2 clicks), Network and Internet (1 click), Click VPN (another click) then fi…
Sending a Secure fax is easy with eFax Corporate (http://www.enterprise.efax.com). First, just open a new email message. In the To field, type your recipient's fax number @efaxsend.com. You can even send a secure international fax — just include t…

912 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

Need Help in Real-Time?

Connect with top rated Experts

16 Experts available now in Live!

Get 1:1 Help Now