LinuxQuestions.org
Download your favorite Linux distribution at LQ ISO.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices


Reply
  Search this Thread
Old 02-01-2004, 12:54 PM   #1
mcshen
LQ Newbie
 
Registered: Dec 2003
Distribution: womandrake
Posts: 28

Rep: Reputation: 15
find repeated characters in a string


How would I go about finding the locations of the repeated character in a string(or array). say, if I have

HIMYDIFIWAI

then, it will return

1,5,7,10
 
Old 02-01-2004, 01:12 PM   #2
jtshaw
Senior Member
 
Registered: Nov 2000
Location: Seattle, WA USA
Distribution: Ubuntu @ Home, RHEL @ Work
Posts: 3,892
Blog Entries: 1

Rep: Reputation: 67
Well, one way I might do it is to make a dynamic array of structs. The struct would contain a counter and a character. Each time I find a new character I add it to the dynamic array of structs and set the counter for it's node to 1. Each time I have a repeat I would increment the counter for the character. Course, there is probably an easier way, I don't do well thinking about coding algorithms after 2 hours of tail gate partying
 
Old 02-01-2004, 02:35 PM   #3
david_ross
Moderator
 
Registered: Mar 2003
Location: Scotland
Distribution: Slackware, RedHat, Debian
Posts: 12,047

Rep: Reputation: 66
Since you never gave a language, here's one in perl
Code:
#!/usr/bin/perl

$string="HIMYDIFIWAI";

$num=0;
foreach $char (split(//,$string)){
$str=$string;
$count = $str =~ s/$char//g;
if($count>1){print $num.", "}
$num++;
}

exit;
 
Old 02-01-2004, 03:42 PM   #4
Strike
Member
 
Registered: Jun 2001
Location: Houston, TX, USA
Distribution: Debian
Posts: 569

Rep: Reputation: 31
The problem definition isn't very clear. No language specified, and is it always going to be just one character that's repeated in the string?
 
Old 02-01-2004, 06:32 PM   #5
mcshen
LQ Newbie
 
Registered: Dec 2003
Distribution: womandrake
Posts: 28

Original Poster
Rep: Reputation: 15
not one character. maybe more than one chars that are repeated.

language: java

thx
 
Old 02-02-2004, 11:21 AM   #6
caged
Member
 
Registered: Jan 2004
Location: new zealand
Distribution: Mandrake,Slackware
Posts: 165

Rep: Reputation: 30
have the program loop through for each charector in the string checking if their are duplicates, skipping charAt(n) where n is the value of any char already defined as a duplicate of another.
 
Old 02-02-2004, 03:44 PM   #7
Strike
Member
 
Registered: Jun 2001
Location: Houston, TX, USA
Distribution: Debian
Posts: 569

Rep: Reputation: 31
A simpler way to do this would be to loop through the string once, keeping a mapping of the letters to their positions in the string. Then, once this is done, just check the mapping for letters with more than one position in the string. This is O(n) behavior.
 
Old 02-02-2004, 03:55 PM   #8
jtshaw
Senior Member
 
Registered: Nov 2000
Location: Seattle, WA USA
Distribution: Ubuntu @ Home, RHEL @ Work
Posts: 3,892
Blog Entries: 1

Rep: Reputation: 67
I like Strikes idea, that was what I was trying to get at with my original post.
 
Old 02-02-2004, 05:06 PM   #9
Strike
Member
 
Registered: Jun 2001
Location: Houston, TX, USA
Distribution: Debian
Posts: 569

Rep: Reputation: 31
The python version (which is probably at least somewhat understandable to non-Pythoners who have some programming experience) would be:

Code:
s = "some string, of course"
pos_map= {}

for pos, char in enumerate(s):
    if char in pos_map:
        pos_map[char].append(pos)
    else:
        pos_map[char] = [pos]

for char, pos_list in pos_map.items():
    if len(pos_list) > 1:
        print "%r -> %r" % (char, pos_list)
For that string ("some string, of course") above, this returns:
Code:
' ' -> [4, 12, 15]
'e' -> [3, 21]
'o' -> [1, 13, 17]
's' -> [0, 5, 20]
'r' -> [7, 19]

Last edited by Strike; 02-02-2004 at 05:10 PM.
 
Old 02-02-2004, 06:43 PM   #10
Looking_Lost
Senior Member
 
Registered: Apr 2003
Location: Eire
Distribution: Slackware 12.0, OpenSuse 10.3
Posts: 1,120

Rep: Reputation: 45
How about this, although admittedly only tested it on two different strings

Code:
import java.util.ArrayList;

public class test
{
 public static void main(String args[])
 {

   String s1=new String("HIMDIFIWAI");
                            
   ArrayList results=new ArrayList();
    char tempChar;                        

  for(int i=0; i<s1.length(); i++)
   {
      tempChar=s1.charAt(i);

     if( s1.indexOf(tempChar)!=s1.lastIndexOf(tempChar))
       {
         results.add(new Integer(i));
        }
    }


   for(int i=0; i<results.size(); i++)
     System.out.print(results.get(i)+",");

 }
}

Last edited by Looking_Lost; 02-02-2004 at 06:50 PM.
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
Find a value following a string sgracelin Linux - Newbie 1 07-22-2005 09:41 AM
How to find a string in a directory? iclinux Linux - Newbie 2 07-02-2005 09:20 AM
exploding string into individual characters using a shell script farmerjoe Programming 9 10-13-2004 04:23 AM
extracting first n characters of a string in perl ananthbv Programming 4 09-14-2004 08:25 AM
Handle escape characters in a string Helene Programming 7 05-02-2004 12:43 AM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 06:03 AM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration