8 Replies - 4437 Views - Last Post: 27 May 2012 - 01:39 AM Rate Topic: -----

#1 indyarocks  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 104
  • Joined: 07-March 12

strings S1 & S2.Delete from S1 all those characters,which occur in

Posted 25 May 2012 - 08:28 AM

Hi Guys,
I'm trying to write a function, which does following;
Given two strings S1 and S2. Delete from S1 all those characters, which occur in S2.

for example:
S1 = abcdefghijklabcdefghii
S2 = ibk

function prototype is : string removeOccurences(string a, string B );
Then the return string should be acdefghjlacdefgh

When I tried to find the length of string, the first issue I faced was:
#include <iostream>
#include <string.h>
string removeOccurences(string a, string B)/>
{ int LenA = strlen(a);
  int LenB = strlen(B)/>;

...
...
}


C:\CodeBlock\Project1\main.cpp|6|error: cannot convert 'std::string' to 'const char*' for argument '1' to 'size_t strlen(const char*)'|


I got around this by:
int LenA ;
for(LenA = 0; a[LenA] != '\0'; LenA++);

Is this the way we find the length of string ? I'm bit confused between "char" array and string.
Now, when I have the length of string, I was thinking of writing a function, which will simply remove the character common with string S2.
But how do we do that ?
for(int i = 0; i < lenA; i++)
{
for(int j = 0; j < lenB; j++)
{
 if(a[i] == b[j]
 {a[i] = '';}
...
}
}

This doesn't seems to be the right way to do it. Can we have a null character inside a string, like I stated above in code snippet ?
Assuming this is not allowed, I was thinking of shifting the character of string a by one left, but it will be time consuming if we have a very large string. Is that right approach to do this ?

An alternate I was thinking is, define a new char array "char c[lenA]" and put the character of string S1, which doesn't matches with any of character of string S2. Now trying to implement this. Any suggestions ?

I hope, I'm expressing my doubt properly. In case, its not, please let me know.

Thanks,
Indy

This post has been edited by indyarocks: 25 May 2012 - 08:31 AM


Is This A Good Question/Topic? 0
  • +

Replies To: strings S1 & S2.Delete from S1 all those characters,which occur in

#2 jimblumberg  Icon User is online

  • member icon


Reputation: 4003
  • View blog
  • Posts: 12,354
  • Joined: 25-December 09

Re: strings S1 & S2.Delete from S1 all those characters,which occur in

Posted 25 May 2012 - 08:35 AM

You seem to be using std::string so you don't want to try to use the C-string (nul terminated character array) functions, like strlen(). You need to include the <string> header, notice no file extension and use one of the std::string member functions. Something like std::string.erase() might do exactly what you want.

Jim
Was This Post Helpful? 1
  • +
  • -

#3 aresh  Icon User is offline

  • It's a 16-Bit World!
  • member icon

Reputation: 273
  • View blog
  • Posts: 4,163
  • Joined: 08-January 12

Re: strings S1 & S2.Delete from S1 all those characters,which occur in

Posted 25 May 2012 - 08:44 AM

As jim mentioned, you are confusing c-string and std::string. If you are using std::string, use str.size() or str.length() instead of strlen(str) to get the size of your string. Since you are using std::string, use <string> library instead of <string.h> since <string.h> is only for c-strings.
Was This Post Helpful? 1
  • +
  • -

#4 jimblumberg  Icon User is online

  • member icon


Reputation: 4003
  • View blog
  • Posts: 12,354
  • Joined: 25-December 09

Re: strings S1 & S2.Delete from S1 all those characters,which occur in

Posted 25 May 2012 - 08:46 AM

And don't forget in C++ <string.h> should actually be <cstring>, use the C++ standard headers in C++ not the C standard headers, there are differences.


Jim
Was This Post Helpful? 1
  • +
  • -

#5 indyarocks  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 104
  • Joined: 07-March 12

Re: strings S1 & S2.Delete from S1 all those characters,which occur in

Posted 25 May 2012 - 09:39 AM

Thanks Jim & Aresh. This helps. Going through the string class :)
Was This Post Helpful? 0
  • +
  • -

#6 indyarocks  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 104
  • Joined: 07-March 12

Re: strings S1 & S2.Delete from S1 all those characters,which occur in

Posted 26 May 2012 - 09:34 PM

Hi,
I'm trying to solve few problems related to strings, In most of the cases, I know how to go about it(algorithm), but I don't know how to implement it using "strings".

For example:
//This program finds out, if given two strings are anagram or no?

#include <iostream>
#include <stdlib.h>
using namespace std;

bool Anagram(string a,string B)/>
{
    int LenA = a.size();
    int LenB = b.size();
    if(LenA != LenB)
    return 0;
    string::iterator iA;
    string::iterator iB;
// Now there are two ways to accomplish this:
// 1. Arrange each string in alphabetical order and just compare them. 
// NOTE: Here compare is easy, a.compare(B)/>; but how to arrange them in alphabetical order ? (Character repetition allowed)
// 2. Count each character in each string, and compare if the count of each characters in a matches with count of each characters in b .
    return 0;

}
int main()
{
    string s1,s2;
    cout << "Enter string S1" << endl;
    cin >> s1;
    cout << "Enter string S2" << endl;
    cin >> s2;
    if(Anagram(s1,s2))
    {
        cout << "String :" << s1 << " and String : " << s2 << " are anagram.\n";
    }
    else
    {
        cout << "String :" << s1 << " and String : " << s2 << " are NOT anagram.\n";
    }
    return 0;
}


As Jim has suggested, I've gone through the cplusplus link for string. But I'm not yet able to organize it to solve problem. Want to see some working example, or concepts on, how to implement the two approach I have described in above code snippet. Please help.

EDIT: Though solved this using second algorithm, still help on my first algorithm described above, will be very much appreciated.(In that the main problem is to sort the string).
//This program finds out, if given two strings are anagram or no?
//Assumming all strings are defined in lower alphabets.
#include <iostream>
using namespace std;

int MapCharacterToNumber(char ch)
{
    return ((int)ch - 97); // ASCII code for 'a' = 97
}
bool Anagram(string a,string B)/>
{
    int LenA = a.size();
    int LenB = b.size();
    if(LenA != LenB)
    return 0;
    string::iterator iA;
    string::iterator iB;
    int index;
    int countChar[26];  //Make an array of size 26, keep track of frequency of match of each alphabet. a - 0, b - 1...z - 25
    for(int i = 0; i < 26; i++) //Initialize the count for each character to 0 .
    countChar[i] = 0;
    for(iA = a.begin(); iA < a.end(); iA++)
    {
        index = MapCharacterToNumber(*iA);
        countChar[index] += 1;
    }
    for(iB = b.begin(); iB < b.end(); iB++)
    {
        index = MapCharacterToNumber(*iB);
        countChar[index] -= 1;
    }
    for(int k = 0; k < 26; k++)
    {
        if(countChar[k] != 0)
        return 0;
    }
    return 1;
}
int main()
{
    string s1,s2;
    cout << "Enter only lower case" << endl;
    cout << "Enter string S1" << endl;
    cin >> s1;
    cout << "Enter string S2" << endl;
    cin >> s2;
    if(Anagram(s1,s2))
    {
        cout << "String :" << s1 << " and String : " << s2 << " are anagram.\n";
    }
    else
    {
        cout << "String :" << s1 << " and String : " << s2 << " are NOT anagram.\n";
    }
    return 0;
}


This post has been edited by indyarocks: 26 May 2012 - 10:15 PM

Was This Post Helpful? 0
  • +
  • -

#7 indyarocks  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 104
  • Joined: 07-March 12

Re: strings S1 & S2.Delete from S1 all those characters,which occur in

Posted 26 May 2012 - 09:40 PM

View Postjimblumberg, on 25 May 2012 - 08:35 AM, said:

You seem to be using std::string so you don't want to try to use the C-string (nul terminated character array) functions, like strlen(). You need to include the <string> header, notice no file extension and use one of the std::string member functions. Something like std::string.erase() might do exactly what you want.

Jim


Thanks Jim. Here is my working code, never knew it was so simple:
#include <iostream>
#include <string>
using namespace std;

string removeOccurences(string a, string B)/> {
int LenA = a.size();
int LenB = b.size();
string::iterator itA;
string::iterator itB;
for(itA = a.begin(); itA < a.end(); itA++)
{
    for(itB = b.begin(); itB < b.end(); itB++)
    {
        if(*itA == *itB)
        {
            a.erase(itA);
        }
    }
}
return a;
}

int main()
{
    string s1 = "abcdefgh";
    string s2 = "ah";
    cout << removeOccurences(s1,s2);
    return 0;
}


Also, thank Aresh :)
But I'm facing some other issue, related to strings, as Mentioned in my previous post. Please help.

This post has been edited by indyarocks: 26 May 2012 - 09:42 PM

Was This Post Helpful? 0
  • +
  • -

#8 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1622
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

Re: strings S1 & S2.Delete from S1 all those characters,which occur in

Posted 26 May 2012 - 10:24 PM

after you call 'erase' it invalidates all of the iterators. so after line 16 is executed, all the iterators your using for 'a' are undefined. I would have a another string the add values to rather than erasing values from 'a'. this way no modification happens to 'a' so none of it's items are invalidated.

there is also the algorithm "set_diffrence" in <algorithm> that does just this.

for it to be of any use you will also need <iterator> for it's back_inserter or inserter functions. you will also have to sort the elements as a requirement of algorithm.

std::string temp;
std::sort(a.begin(), a.end());
std::sort(b.begin(), b.end());
set_difference(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(temp));
return temp;



however, your algorithm that *YOU* made will work perfectly fine with a bit of modification and I would encourage that you use it. all you have to do is add the character of 'a' if it can't be found in 'b' you can loop though 'a' to get each character then loop though 'b' to determine if the current character is in b. after that loop is done then if the character wasn't found then add it to 'temp'. after each character of 'a' has been checked return 'temp'

you can add a value to a string using str.push_back('c') or using the += operator. I like the += operator but it doesn't really matter.

std::string s = "hello, world"
s += '!';
std::cout<<s; //prints "hello, world!"



P.S. set_diffrence is exactly the kind of thing that I love the <iterator> and <algorithm> libraries for :)

also if you are using C++11 then you can use the 'auto' keyword.

rather than typeing 'std::string::iterator itA' you can just declare in the loop like so. I'm pretty sure VC++ supports this

for(auto itA = a.begin(); itA != itA.end(); ++itA)



OOOOOOOOR if you have GCC 4.6 or higher then you can use the even more succulent range based for loop

for(auto ac : a) {
   for(auto bc : B)/> {
      //'ac' is same as *itA
      //'bc' is same as *itB
   }
}



C++11 has some really cool things in it ;)

some experts(like bjarne stroustrup, the creator of C++) actually say to use the 'for_each' algorithm for this becuase you instantly know you are iterating over a container when you read it. the key here is to use another C++11 fetures, lambda functions(VC++ supports these as well as GCC 4.4 and above)

std::for_each(begin(a), end(a), [&](char ac) {
   std::for_each(begin(B)/>, end(B)/>, [&](char bc) {
      //ac and bc are like they above in the range based for loop
   });
});



with gcc you need to pass it the option std=C++0x to use C++11 features. if you are using gcc 4.7(latest) then you use std=C++11.

This post has been edited by ishkabible: 26 May 2012 - 10:43 PM

Was This Post Helpful? 1
  • +
  • -

#9 aresh  Icon User is offline

  • It's a 16-Bit World!
  • member icon

Reputation: 273
  • View blog
  • Posts: 4,163
  • Joined: 08-January 12

Re: strings S1 & S2.Delete from S1 all those characters,which occur in

Posted 27 May 2012 - 01:39 AM

I am not saying that this is the most effective way, but it is an easy way to sort the string.. Here it is :
string string_sort(string s1)
{
    int size=s1.size();
    for(int i=0;i<size;i++)
    {
            for(int j=0;j<size;j++)
            {
                    if(s1[i]<s1[j])
                    {
                                   char temp=s1[i];
                                   s1[i]=s1[j];
                                   s1[j]=temp;
                    }
            }
    }
    return s1;
}


This function compares each and every element with other elements of the string, and is not the most efficient algorithm around.. But still, it will do your work :D
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1