Tuesday, December 8, 2009

Find the First Nonrepeated Character

/*
Write a function to find the first nonrepeated character in a string. For instance, the first nonrepeated character in “total” is ‘o’ and the first nonrepeated character in “teeter” is ‘r’.
*/
public static Character firstNonRepeated( String str )
{
    Hashtable charHash = new Hashtable();
    int i, length;
    Character c;
    Object seenOnce = new Object();
    Object seenTwice = new Object();

    length = str.length();

    // Scan str, building hash table
    for( i = 0; i < length; i++ )
    {
        c = new Character(str.charAt(i));
        Object o = charHash.get(c);
        if( o == null )
        {
            charHash.put( c, seenOnce );
        }
        else if( o == seenOnce )
        {
            // Increment count corresponding to c
            charHash.put( c, seenTwice );
        }
    }

    // Search hashtable in order of str
    for( i = 0; i < length; i++ )
    {
        c = new Character(str.charAt(i));
        if( charHash.get(c) == seenOnce )
        {
            return c;
        }
    }
    return null;
}

No comments:

Post a Comment