wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> puzzle: find first non repeated character
        
(Message started by: puzzlecracker on Dec 9^th, 2004, 5:48pm)

Title: puzzle: find first non repeated character
Post by puzzlecracker on Dec 9^th, 2004, 5:48pm

Given an array of characters in array find first non-repeated character. ex. in "total" is 'o'

Title: Re: puzzle: find first non repeated character
Post by Grimbal on Dec 10^th, 2004, 5:57am

Create an array of flags, one per character, set them to false.
Scan the string from the end. For each character: if the flag is false save the character and set the flag to true.
When done, the last saved character is the first non-repeated.
Advantage: for large strings, it is still O(n).
Problem: for short strings and large character sets, you still have to initialize the whole array of flags.

Title: Re: puzzle: find first non repeated character
Post by puzzlecracker on Dec 10^th, 2004, 9:34am

where are you going to save the characters? create another array?

Title: Re: puzzle: find first non repeated character
Post by Grimbal on Dec 14^th, 2004, 3:35am

yes. If the character set is fixed, it is O(1).

Title: Re: puzzle: find first non repeated character
Post by Margit on Dec 16^th, 2004, 12:47am

How does that work with eg. "AAB" ?

Title: Re: puzzle: find first non repeated character
Post by puzzlecracker on Dec 16^th, 2004, 2:14pm

Hi I just wrote the alg based on your psuedo code, but it doesnt work:

#include<iostream>
using namespace std;

int main()
{
bool charFlag[26];
char chars[26], *in="total";
int last=-1;

for(int i=0;i<26;charFlag[i]=false,i++); // clear the flag arr

for(int i=0;i<=sizeof(in);i++)
{
if(charFlag[in[i]-'a']==true)
continue;
charFlag[in[i]-'a']=true;
chars[++last]=in[i];
}

cout<<chars[last]<<endl;
system("PAUSE");
return 0;
}

Title: Re: puzzle: find first non repeated character
Post by puzzlecracker on Dec 16^th, 2004, 2:17pm

Hi I just wrote the alg based on your psuedo code, but it doesnt work: (playing with code funcs :))

Code:

#include<iostream>
using namespace std;

int main()
{
bool charFlag[26];
char chars[26], *in="total";
int last=-1;

for(int i=0;i<26;charFlag[i]=false,i++); // clear the flag arr

for(int i=0;i<=sizeof(in);i++)
{
if(charFlag[in[i]-'a']==true)
continue;
charFlag[in[i]-'a']=true;
chars[++last]=in[i];
}

cout<<chars[last]<<endl;
system("PAUSE");
return 0;
}

Title: Re: puzzle: find first non repeated character
Post by towr on Dec 16^th, 2004, 2:35pm

I think you missed the 'from the end' part.
Start at the end of the string, and scan to the front.

Title: Re: puzzle: find first non repeated character
Post by puzzlecracker on Dec 16^th, 2004, 3:24pm

Sorry, forgot to traverse in reverse... the problem is actually valid of aab... it iwll report a is a last stored char.....

Code:

i
#nclude<iostream>
using namespace std;

int main()
{
bool charFlag[26];
char chars[26], *in="aab";
int last=-1;

for(int i=0;i<26;charFlag[i]=false,i++); // clear the flag arr

for(int i=sizeof(in)+1;i>=0;i--)
{
if(charFlag[in[i]-'a'])
continue;
charFlag[in[i]-'a']=true;

last =i;

}

cout<<in[last]<<endl;
system("PAUSE");
return 0;
}

Title: Re: puzzle: find first non repeated character
Post by puzzlecracker on Dec 16^th, 2004, 5:45pm

oK sorry for the bombardment: here is the correct solution to the problem

create a hashtable for each char,
zero out every element
for every occurance of the character, increment the coutner
go through string array again and if that char hashes to 1, return it.

i implemented hash using array

Code:

#include<iostream>
using namespace std;

int main()
{
int charFlag[26];
char *in="aab";

for(int i=0;i<26;charFlag[i]=0,i++); // clear the flag arr

for(int i=0;i<=sizeof(in);++i)
charFlag[in[i]-'a']++;
for(int i=0;i<=sizeof(in);++i)
if(charFlag[in[i]-'a']==1){
cout<<in[i]<<endl;
break;
}

system("PAUSE");
return 0;
}